[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;
}
}
}