0

我如何使用蛮力（朴素算法）检查一个 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);
    }
    }
4

1 回答 1

0

我猜你的意思是 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,648to 2,147,483,647，所以它不能保留 16 位数字。您可以使用long，因为它的范围是-9,223,372,036,854,775,808to 9,223,372,036,854,775,807，所以它可以容纳 16 位数字。

于 2019-03-05T16:12:03.660 回答