素數算法

Question

誰能告訴我如何在C中實現Sieve of Eratosthenes算法？我需要生成素數，但我的算法很慢。

我的代碼：

#include <stdio.h> 

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

您需要創建一個與您想要查找的最大質數一樣大的布爾值數組。在開始時，它被完全初始化爲真。

如果i是質數，則此數組的i單元格將爲真，如果不是，則爲false。

開始從i=2迭代：它是素數，則設置爲與2圍棋的指標多至下一個素數（i=3）任何虛假細胞，做同樣的。轉到下一個素數（它是i=5：i=4不是素數：array[4]在處理i=2時被設置爲false）並且一次又一次地執行相同操作。

Answer 2

Marc B的鏈接顯示了一個非常簡單的算法，它是正確的，由NSLogan編寫。我寫了一個小小的修改來顯示一些大小/速度的權衡。我以爲我會爲了利益而分享。

首先，代碼：

#include <stdio.h> 
#include <stdlib.h> 
#include <math.h> 
#include <assert.h> 
#include <time.h> 

#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 個字符：5.8S M-話：10.8s

有趣的是，即使所有的醜陋表示只有一位的布爾值所需的位移總體上仍然較快。我的推測是緩存和參考地點似乎超過額外的〜3條指令。另外，你最終會使用n位機器字方法的1/n的內存！

Answer 3

在我看來，你的算法很慢，因爲你計算了無關的數字。 試試這個代碼

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 4

雖然這是很老的文章，以下是我嘗試生成使用「的埃拉托色尼篩」算法素數。

#include <stdio.h> 

#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<NUM; i++, j++) 
    { 
    a[j] =i; 
    } 


    for(i = 0; i < NUM; i++) 
    { 
    int num = a[i]; 

    /* If number is not 0 then only update the later array index. */ 
    if(num != 0) 
    { 
     for (j = i+1; j < NUM; j++) 
     { 
     if((a[j]%num == 0)) 
     { 
      a[j]=0; 
     } 
     } 
    } 
    } 


    for(i = 0; i < NUM; i++) 
    { 
    /* Print all the non Zero *Prime numbers* */ 
    if(a[i] != 0) 
    { 
     printf("%d \n", a[i]); 
    } 
    } 

} 

希望這會幫助別人。

Answer 5

這裏實際上是非常簡單的代碼，它使用了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; 
}