素数生成器需要一定范围内的素数。
输入:
输入以单行中的测试用例数 t 开头 (t<=10)。在接下来的 t 行中，每一行都有两个数字 m 和 n
(1 <= m <= n <= 1000000000, n-m<=100000) 以空格分隔。
输出:
对于每个测试用例，打印所有素数 p 使得 m <= p <= n，每行一个数字，用空行分隔测试用例。
我的程序使用此解决方案运行完美，但超过了时间限制，因此未被接受为解决方案。
我用 scanf 和 printf 替换了 cin 和 cout。
我已经用 while 循环替换了 for 循环，什么不是。我可以采取哪些其他措施来加快我的解决方案？
#include<iostream>
int prime(unsigned long int p)
{
int f=1,i=2;
while(i<=p/2)
{
if(p%i==0)
{ f=0;
break;
}
++i;
}
if(f==1)
{ printf("%d \n",p);
}
return 0;
}
int main()
{
int t, i=0;
unsigned long int m,n,j;
scanf("%d",&t);
while(i<t)
{
scanf("%lu%lu",&m,&n);
for(j=m;j<=n;++j)
{
if(j!=1&&j!=0)
prime(j);
}
printf("\n");
++i;
}
return 0;
}
您的代码效率低下，因为您使用的是一种缓慢的算法来查找素数。将 for 循环更改为 while 循环可能不会加快代码速度，但更改为更好的算法会。
更快的算法:
有一种非常简单的算法，称为埃拉托色尼筛法。我们首先制作一个 bool 数组。将它们全部标记为真。这个数组将让我们跟踪哪些数字是质数，哪些不是质数。我们将划掉我们知道不是质数的那些(通过将它们设置为 false)。
- 从数组中划掉0和1
- 从 4 开始，划掉所有 2 的倍数
- 从 6 开始，划掉所有 3 的倍数
- 从 10 开始，划掉所有 5 的倍数
- 从 14 开始，划掉所有 7 的倍数
- (继续这个过程)
例子:
// takes a reference to a vector of bools
// a vector is a resizable array
void cross_out_multiples(std::vector<bool>& primes, int num) {
for(int i = num * 2; i < primes.size(); i += num) {
primes[i] = false;
}
}
std::vector<int> findPrimes(int max) {
std::vector<bool> primes(max); // create array with max elements
for(int i = 0; i < max; ++i) {
primes[i] = true;
}
// 0 and 1 aren’t prime, so we mark them false
primes[0] = false;
primes[1] = false;
// here we mark multiples of n false
for(int n = 2; n < max; n++) {
// if a number isn’t prime, we can skip it
if(not primes[n]) {
continue;
}
// if n squared is bigger than max, we already
// crossed out all multiples of n smaller than max
// so we don’t have any more work to do
if(n * n > max) {
break;
}
// now we just cross out multiples of n
cross_out_multiples(primes, n);
}
// now, take the numbers that are prime:
std::vector<int> listOfPrimes;
for(int i = 0; i < max; i++) {
// if a number is prime, add it to the list
if(primes[i]) {
listOfPrimes.push_back(i);
}
}
return listOfPrimes;
}I