素数算法

谁能告诉我如何在C中实现Eratosthenes算法的Sieve ？ 我需要生成素数但我的算法很慢。

我的代码：

#include  int prime(long int i) { long int j; int state = 1; for(j=2;j<i;j++) { if((i%j)==0){state=0;break;} } return state; } int main() { int t; long int m,n,i; scanf("%d", &t); while(t--) { scanf("%d %d", &m,&n); for(i=m;i<=n;i++) { if(i==1){ //do nothing for 1 } else{ if(prime(i))printf("%d\n",i); } } } return 0; } 

t是测试用例的数量m，n是要打印质数的范围。

Answer 1

您需要创建一个与您要查找的最大素数一样大的布尔数组。 在开始时它完全初始化为true。

如果i是素数，则此类数组的第i个单元格将为true，否则为false。

从i=2开始迭代：它是素数，然后设置为任何索引倍数为2的单元格。转到下一个素数（ i=3 ）并执行相同操作。 转到下一个素数（它是i=5 ： i=4不是素数：当处理i=2时， array[4]被设置为假）并且一次又一次地执行相同操作。

Answer 2

在我看来，你的算法很慢，因为你计算了不必要的数字。 试试这段代码

 int isPrime(int number){ if(number < 2) return 0; if(number == 2) return 1; if(number % 2 == 0) return 0; for(int i=3; (i*i)<=number; i+=2){ if(number % i == 0 ) return 0; } return 1; } 

Answer 3

这是使用Eratosthenes Sieve算法的非常简单的代码。 适用于所有积极的int 。

 int is_prime(int n){ int p; for(p = 2; p < n; p++){ if(n % p ==0 && p != n) return 0; } return 1; } 

Answer 4

Marc B的链接显示了一个非常简单的算法，该算法是正确的，由NSLogan编写。 我对它进行了一些修改，以显示一些尺寸/速度权衡。 我以为我会为了感兴趣而分享。

一，代码：

 #include  #include  #include  #include  #include  #define USE_BITS #ifdef USE_BITS #define alloc_prime char *prime = calloc(i/8,sizeof(*prime)); #define set_not_prime(x) prime[x/8]|= (1<<(x%8)) #define is_prime(x) (!(prime[x/8]&(1<<(x%8)))) #endif #ifdef USE_CHAR #define alloc_prime char *prime = calloc(i,sizeof(*prime)); #define set_not_prime(x) prime[x] = 1 #define is_prime(x) (prime[x] == 0) #endif #ifdef USE_SIZE_TYPE #define alloc_prime size_t *prime = calloc(i,sizeof(*prime)); #define set_not_prime(x) prime[x] = 1 #define is_prime(x) (prime[x] == 0) #endif int main(){ int i; printf("Find primes up to: "); scanf("%i",&i); clock_t start, stop; double t = 0.0; assert((start = clock())!=-1); //create prime list alloc_prime; int c1, c2, c3; if(!prime){ printf("Can't allocate %zu bytes!\n",i*sizeof(*prime)); exit(1); } //set 0 and 1 as not prime set_not_prime(0); set_not_prime(1); //find primes then eliminate their multiples (0 = prime, 1 = composite) for(c2 = 2;c2 <= (int)sqrt(i)+1;c2++){ if(is_prime(c2)){ c1=c2; for(c3 = 2*c1;c3 <= i+1; c3 += c1){ set_not_prime(c3); } } } stop = clock(); t = (double) (stop-start)/CLOCKS_PER_SEC; //print primes for(c1 = 0; c1 < i+1; c1++){ if(is_prime(c1))printf("%i\n",c1); // if(prime[c1] == 0) printf("%i\n",c1); } printf("Run time: %f\n", t); //print time to find primes return 0; } 

（原谅错误消息，因为定义了USE_BITS时不准确...）

我已经比较了三种不同的存储peoro建议的布尔变量的方法。 一种方法实际上使用位，第二种方法使用整个字节，最后一种方法使用整个机器字。 关于哪个最快的天真猜测可能是机器字方法，因为每个标志/布尔值都由您的机器更“自然地”处理。 在我的机器上计算高达100,000,000的质数的时间如下：

比特：3.8s Chars：5.8s M-words：10.8s

值得注意的是，即使是只用一位表示布尔值所需的所有丑陋的位移仍然总体上更快。 我的猜想是缓存和引用位置似乎超过了额外的3条指令。 另外，你最终使用n位机器字方法的1 / n内存！

Answer 5

虽然它是一个非常古老的post，但是我试图使用“Eratosthenes筛选”算法生成素数。

 #include  #define NUM 8000 /* Prime Numbers in the Range. 'Range + 2' actually. */ int main() { int a[NUM] = {0}; /* Array which is going to hold all the numbers */ int i , j; /* initializing array from 2 to given number + 2, assuming the first prime number is 2 */ for(i = 2,j=0; i < NUM+2, j 

希望这会对某人有所帮助。