哪种素数生成算法最快?
Which is the quickest of prime generating algorithms?
我正在研究 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。
谁能告诉我为什么这种新方法没有那么快?或者我可以做些什么来进一步改进算法?
提前致谢!
您应该考虑是否有一种方法可以在一个范围内找到 所有 个素数,这比单独检查每个素数要快得多。例如,您将检查许多数字是否可以被 73 整除。但事实是,您可以更快地确定所有可以被 73 整除的数字(它们是 73、2*73、3*73、4*73 等。 ).
顺便说一句:您在循环的每次迭代中计算 Math.sqrt (j)。将该计算移到循环之外可能会使您的代码更快。
你的第二个算法更快。我不知道为什么你只看到了 20% 的改进。以下是我的测试结果,具有单独的实现:
10^6:
First: 00:00:01.0553813 67240405 steps
Second: 00:00:00.2416291 13927398 steps
Sieve: 00:00:00.0269685 3122044 steps
10^7:
First: 00:00:26.4524301 1741210134 steps
Second: 00:00:04.6647486 286144934 steps
Sieve: 00:00:00.3011046 32850047 steps
10^8:
First: 00:12:00.8986644 46474124250 steps
Second: 00:01:43.1543445 6320928466 steps
Sieve: 00:00:03.6146328 342570200 steps
最后一个算法是 Sieve of Eratosthenes,这是一个更好的算法。我在 C# 中为一个处理器实现了所有这些,前两个基于您的代码并进行了一些小的更改,例如测试 primes[j]*primes[j] <= i
。
我使用的埃拉托色尼筛法的实现非常基础,
Boolean[] definitelyComposite = new Boolean[max]; // initialized automatically to false
int p = 0;
for (long i = 2; i < max; i++)
{
numSteps++;
if (!definitelyComposite[i])
{
primes[p] = i;
p++;
for (long j = i * i; j < max; j += i)
{
numSteps++;
definitelyComposite[j] = true;
}
}
}
还有待改进。例如,除了 i 为 2 时,我可以在循环中使用 j+= 2*i
。
我正在研究 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。
谁能告诉我为什么这种新方法没有那么快?或者我可以做些什么来进一步改进算法?
提前致谢!
您应该考虑是否有一种方法可以在一个范围内找到 所有 个素数,这比单独检查每个素数要快得多。例如,您将检查许多数字是否可以被 73 整除。但事实是,您可以更快地确定所有可以被 73 整除的数字(它们是 73、2*73、3*73、4*73 等。 ).
顺便说一句:您在循环的每次迭代中计算 Math.sqrt (j)。将该计算移到循环之外可能会使您的代码更快。
你的第二个算法更快。我不知道为什么你只看到了 20% 的改进。以下是我的测试结果,具有单独的实现:
10^6:
First: 00:00:01.0553813 67240405 steps
Second: 00:00:00.2416291 13927398 steps
Sieve: 00:00:00.0269685 3122044 steps
10^7:
First: 00:00:26.4524301 1741210134 steps
Second: 00:00:04.6647486 286144934 steps
Sieve: 00:00:00.3011046 32850047 steps
10^8:
First: 00:12:00.8986644 46474124250 steps
Second: 00:01:43.1543445 6320928466 steps
Sieve: 00:00:03.6146328 342570200 steps
最后一个算法是 Sieve of Eratosthenes,这是一个更好的算法。我在 C# 中为一个处理器实现了所有这些,前两个基于您的代码并进行了一些小的更改,例如测试 primes[j]*primes[j] <= i
。
我使用的埃拉托色尼筛法的实现非常基础,
Boolean[] definitelyComposite = new Boolean[max]; // initialized automatically to false
int p = 0;
for (long i = 2; i < max; i++)
{
numSteps++;
if (!definitelyComposite[i])
{
primes[p] = i;
p++;
for (long j = i * i; j < max; j += i)
{
numSteps++;
definitelyComposite[j] = true;
}
}
}
还有待改进。例如,除了 i 为 2 时,我可以在循环中使用 j+= 2*i
。