[C/C++ 演算法]- ratosthenes篩選求質數

[C/C++ 演算法]- Eratosthenes篩選求質數

剛才找資料時發現一個C/C++的教學網站，趕快發揮(C/P)的長才將它備份來，有需要的同好，歡迎來(C/P)一下^^。

拷貝來源：
http://openhome.cc/Gossip/AlgorithmGossip/
http://openhome.cc/Gossip/AlgorithmGossip/EratosthenesPrime.htm

#include <stdio.h> 
#include <stdlib.h> 

#define N 1000 

void create(int*);
void filter(int*, int);

int main(void) { 
    int primes[N + 1] = {0};
    create(primes);
    
    int i;
    for(i = 2; i < N; i++) if(primes[i]) { 
        printf("%4d", i); 
    }
 
    return 0; 
} 

void create(int* primes) {
    primes[2] = primes[3] = primes[5] = 1;
    
    int i;
    for(i = 1;6 * i + 5 <= N; i++) {
        primes[6 * i + 1] = primes[6 * i + 5] = 1; 
    }
    if(6 * i + 1 <= N) { primes[6 * i + 1] = 1; }
    
    int n;
    for(n = 0;(6 * n + 5) * (6 * n + 5) <= N; n++) {
        filter(primes, 6 * n + 1);
        filter(primes, 6 * n + 5);
    }     
    if((6 * n + 1) * (6 * n + 1) <= N) { filter(primes, 6 * n + 1); }  
}

void filter(int* primes, int i) {
    if(primes[i]) { 
        int j;
        for(j = 2; j * i <= N; j++) {
            primes[j * i] = 0; 
        }
    }
}