java - 查找大范围内奇数位素数的算法

Question

给定范围 [1, 1000000000]，我们需要找到素数，并且素数的所有数字都必须是奇数。 (例如:23 不行，31 可以) 如果我们继续循环每个数字并检查它是否是素数等，那么速度会非常慢。有没有办法让它接近 O(N) ？ 我试图通过首先查看数字来尽可能地消除。但在消除偶数之后，素数测试就太慢了。

• 对于 [1, N] 中的所有数字
• 检查所有数字，如果有偶数，则继续
• 检查素数(这一步非常慢)

并且素性测试不应该非常复杂(概率等不可能，必须可以在几分钟内实现)。我用的是:

    private static boolean isPrime(int n) {
        boolean isPrime = true;
        for (int divisor = 2; divisor <= n / 2; divisor++) {
            if (n % divisor == 0) {
                isPrime = false;
                break;
            }
        }

        return isPrime;
   }

也许有一个技巧可以确保快速素性测试，但我找不到。有什么建议么？感谢您的阅读。

Answer 1

您不需要检查所有的百万数字。生成所有只有奇数位的数字 - 最多有 5^9~2 百万个。排除以 5 结尾的数字，并且不生成能被 3 整除的数字(在生成最后一位数字时)

然后检查这些数字的素数。请注意，循环限制可能是 sqrt(n)

Ideone

class Ideone
{
   static int oddcnt;

        public static void checkprime(int x) {
           for (int i=3; i <= Math.sqrt(x); i +=2)
              if ((x % i) == 0)
                 return;
             oddcnt++;
        }


    public static void genodd(int x, int curlen, int maxlen) {
        x *= 10;
        for (int i=1; i<10; i+=2) {
            int nx = x + i;
            checkprime(nx);
            if (curlen < maxlen)
                genodd(nx, curlen + 1, maxlen);
        } 
    }

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

    genodd(0, 1, 8);
    System.out.println(oddcnt);
    }
}