java - 计算素数直到N

此代码可以很好地计算素数直到n。问题是，当n值很大（如1000000或更大）时，执行和打印输出将花费很长时间（超过30秒）。我想解决这个问题。任何帮助都会很棒。下面是代码：

public class PrimeNotillN {

        public static void main(String[] args) {

            int n = 1000;
            int count = 0;

            for (int i = 2; i < n; i++) {
                boolean res = checkprime(i);
                if (res == true)
                    count++;
            }
            System.out.println("total prime number till " + n + " is " + count);
        }

        private static boolean checkprime(int n) {
            if (n == 1)
                return false;
            else {
                for (int i = 2; i <= n / 2; i++) {
                    if (n % i == 0) {

                        return false;
                    }
                }

                return true;
            }
        }
    }

最佳答案

最简单的更改是在for到达checkprime的平方根之后结束i中的n循环。原因是，如果找到的因数大于n的平方根，则意味着应该有一个小于n的平方根的因数。

for (int i = 2; i <= Math.sqrt(n); i++) {

此外，如果您需要更高的速度，则打印所有素数到极限的最佳算法是Sieve of Eratosthenes。这涉及替换您拥有的东西。您将需要一个数组，其中要标记哪些数字是复合数字。从2开始，您将2的所有倍数标记为复合。在数组中移动时，如果找到未标记为复合的数字，则它是质数，可以打印出来。遇到每个素数时，也会将所有素数的倍数标记为复合。

关于java - 计算素数直到N，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/30850488/