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);
    }
}