[範例] 質數又來了

質數又來了

這次是給你兩個數字

算出介在這兩者間的質數有幾個

其實差不多，直接看下去吧

1. #include <iostream>
2. #include <vector>
3. using namespace std;
4. const int MAX = 46341;
5. void creat(bool* prime);
6. void filter(bool*, int);
7. int main()
8. {
9.     bool prime[MAX + 1] = {};  //加{}確保每個元素都指向0
10.     creat(prime);
12.     vector<int> prim;
13.     for (int i=0 ;i<MAX; i++)
14.     {
15.         if(prime[i])
16.         {
17.             prim.push_back(i);
18.         }
19.     }
    
21.     int a, b;
22.     while (cin >> a >> b){
23.         int count = 0;
24.        if (b <= MAX)
25.        {
27.            for (int i=a; i<=b; i++)
28.            {
29.                if(prime[i])
30.                {
31.                    count++;
32.                }
33.            }
34.        }
35.        else
36.        {
37.            vector<int>::iterator p;
39.            for (int i=a; i<=b; i++)
40.            {
41.                 int notprime = 0;
42.                 for (p = prim.begin(); p != prim.end(); p++)
43.                 {
44.                     if (i % (*p) == 0)
45.                     {
46.                         notprime = 1;
47.                         break;
48.                     }
49.                 }
50.                 if (notprime == 0)
51.                 count++;
52.            }
53.        }
54.        cout << count << endl;
55.     }
56. }
57. //創造質數表
58. void creat(bool* prime)
59. {
60.     prime[2] = prime[3] = prime[5] = 1;
61.     //把6n+1、6n+5全設為質數
62.     int i;
63.     for (i=1; 6*i+5 <= MAX; i++)
64.     {
65.         prime[6*i+5] = prime[6*i+1] = 1;
66.     }
67.     if (prime[6*i+1] <= MAX)
68.     {
69.         prime[6*i+1] = 1;
70.     }
71.     //然後過濾掉6n+1、6n+5的倍數皆不為質數
72.     int j;
73.     for (j=0; (6*j+5)*(6*j+5) <= MAX; j++)
74.     {
75.        filter(prime, 6*j+5);
76.        filter(prime, 6*j+1);
77.     }
78.     if (prime[6*j+1] <= MAX)
79.     {
80.         filter(prime, 6*j+1);
81.     }
82. }
83. //過濾掉質數的倍數
84. void filter(bool* prime, int i)
85. {
86.     if (prime[i])
87.     {
88.         for (int j=2; i*j <= MAX; j++)
89.             prime[i*j] = 0;
90.     }
91. }