Brute Force素数检查16位长整数

Question

我如何使用强力（天真算法）来检查16位长整数是否为素数并打印之前的所有素数。数字示例：1254786951475276。这是我的代码：

   import java.io.*;

public class PrimeNumbers {

    public static boolean checkPrime(long n)
    {
        if (n % 2 == 0)
            return false;

        for (int i = 3; i <= Math.sqrt(n); i += 2) 
        {
            if (n % i == 0)
                return false;
        }

        return true;
    }

    public static void generatePrimeNumbers(long n) {

        for (int i = 2; i<= n-1 ; i++) {

            if (checkPrime(i)) {
                System.out.println(i);
            }
        }
    }

    public static void main(String args[]) throws Exception{

        BufferedReader br = new BufferedReader (new InputStreamReader(System.in));

        long n = 0;
        n = Integer.parseInt(br.readLine());

        generatePrimeNumbers(n);
    }
    }

Answer 1

我猜你的意思是16位，而不是16位。 16位非常简单，你可以通过一个简单的循环和除法来检查它。您的checkPrime()可以像这样进行优化：

public static boolean checkPrime(long n)
{
    if (n == 2)
        return true;

    if (n % 2 == 0)
        return false;

    for (long i = 3; i <= Math.sqrt(n); i += 2) 
    {
        if (n % i == 0)
            return false;
    }

    return true;
}

但是如果数字太大（我认为即使是16位数，也没有必要），你可以使用Miller-robin primality test。此测试可用于检查非常大的数字是否为素数。

如果您需要生成所有素数直到特定数字，您可以使用Sieve of Eratosthenes。

请记住，int范围是-2,147,483,648到2,147,483,647，所以它不能保持16位数字。您可以使用long，因为它的范围是-9,223,372,036,854,775,808到9,223,372,036,854,775,807，因此它可以容纳16位数字。