[prime] 簡易質數表

這是利用6n+1 , 6n+5篩選的質數表

原理是一個數字可以分解成 : 6n,  6n+1, 6n +2, 6n+3, 6n+4, 6n+5
其中6n、6n+2、6n+4可以被2整除，6n + 3可以被3整除，
因此只要處理6n+1、6n+5的數即可。



ps.對於更大的質數就要另外處理了。

1. #include <iostream>
2. using namespace std;
3. const int MAX = 46341;
6. void creat(bool* prime);
7. void filter(bool*, int);
9. int main()
10. {
12.     bool prime[MAX + 1] = {};  //加{}確保每個元素都指向0
13.     creat(prime);
14.     int n1;
15.     while (cin >> n1){
16.         if(prime[n1])
17.             cout << "質數\n";
18.         else
19.             cout << "非質數\n";
21.     }
22. }
24. //創造質數表
25. void creat(bool* prime)
26. {
27.     prime[2] = prime[3] = prime[5] = 1;
29.     //把6n+1、6n+5全設為質數
30.     int i;
31.     for (i=1; 6*i+5 <= MAX; i++)
32.     {
33.         prime[6*i+5] = prime[6*i+1] = 1;
34.     }
35.     if (prime[6*i+1] <= MAX)
36.     {
37.         prime[6*i+1] = 1;
38.     }
40.     //然後過濾掉6n+1、6n+5的倍數皆不為質數
41.     int j;
42.     for (j=0; (6*j+5)*(6*j+5) <= MAX; j++)
43.     {
44.        filter(prime, 6*j+5);
45.        filter(prime, 6*j+1);
46.     }
47.     if (prime[6*j+1] <= MAX)
48.     {
49.         filter(prime, 6*j+1);
50.     }
52. }
54. //過濾掉質數的倍數
55. void filter(bool* prime, int i)
56. {
57.     if (prime[i])
58.     {
59.         for (int j=2; i*j <= MAX; j++)
60.             prime[i*j] = 0;
61.     }
62. }