performance - 哪种素数生成算法最快？

Question

我当时正在研究一种 Java 算法，用于查找不超过某个数的所有素数。它应该是对早期方法的改进，如下所示:

public static int[] generatePrimesUpTo(int max)
{
    int[] primes = new int[max];
    primes[0]=2;
    int p = 1;
    for (int i=3;i<max;i+=2)
    {
        if (isPrime(i))
        {
            primes[p]=i;
            p+=1;
        }
    }
    return primes;  
}

public static boolean isPrime(int a)
{
    for (int i=3;i<((int)Math.sqrt(a)+1);i+=2)
    {
        if (a%i==0)
            return false;
    }
    return true;
}

它只是检查一个数字 N 是否可以被一个较小的数字整除，从 2 开始到 sqrt(N) 结束。

现在，新方法是将 N 仅除以算法之前发现的较小素数。我认为它会大大加快这个过程，因为它需要做的计算要少得多。

public static int[] generatePrimes(int num)
{
    int[] primes = new int[num];
    int p = 3;
    primes[0] = 2;
    primes[1] = 3;
    primes[2] = 5;
    boolean prime;
    for (int i=7;i<num;i+=2)
    {
        prime = true;
        for (int j=0;primes[j+1]<(Math.sqrt(i)+1);j++)
        {
            if (i%primes[j]==0)
            {
                prime = false;
                break;
            }
        }
        if (prime)
        {
            primes[p]=i;
            p++;
        }
    }
    return primes;
}

但是，对于Nmax = 10^7，速度似乎几乎没有差异。 对于 Nmax = 10^8，新的快了 20%，但我的计算机在旧的计算过程中更加活跃，我只尝试了一次 10^8。

谁能告诉我为什么这种新方法没有那么快？或者我可以做些什么来进一步改进算法？

提前致谢!

Answer 1

您应该考虑是否有一种方法可以比单独检查每个素数更快地找到范围内的所有 素数。例如，您将检查许多数字是否可以被 73 整除。但事实是，您可以更快地确定所有可以被 73 整除的数字(它们是 73、2*73、3*73、4*73 等。 ).

顺便说一句:您在循环的每次迭代中计算 Math.sqrt (j)。将该计算移到循环之外可能会使您的代码更快。