Elementary methods in number theory exercise 1.5.1 暨 重启C++之路:列出1到210的所有素数

自从大一自学了一点C++后,好久没玩C++了,忘了不少.毕竟算一门手艺(只有数学,物理这种大道式的学科才能算一门学问,C++这种根据计算机学家的脾气不断改变的编程语言在我眼里就是一个玩具),说不定将来快饿死的时候还能用来谋生.因此我决定以此博文重启C++学习之路.今天一道数论题叫我用Eratosthenes筛法列出从1到210的素数,这太麻烦了,因此这件事情要C++来干.

1 #include<iostream>
2 using namespace std;
3 int main()
4 { 
5 for (int i=1;i<=210;i++)
6 {cout<< i<<",";
7 }
8 return 0;
9 }

得到的结果是:

1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100,101,102,103,104,105,106,107,108,109,110,111,112,113,114,115,116,117,118,119,120,121,122,123,124,125,126,127,128,129,130,131,132,133,134,135,136,137,138,139,140,141,142,143,144,145,146,147,148,149,150,151,152,153,154,155,156,157,158,159,160,161,162,163,164,165,166,167,168,169,170,171,172,173,174,175,176,177,178,179,180,181,182,183,184,185,186,187,188,189,190,191,192,193,194,195,196,197,198,199,200,201,202,203,204,205,206,207,208,209,210

然后删去所有2的倍数:

1 #include<iostream>
 2 using namespace std;
 3 int main()
 4 { 
 5 for (int i=1;i<=210;i++)
 6 {
 7     if (i%2==0)
 8 
 9 {
10     i=i;
11 }
12 else
13 
14 {
15     cout<<i<<",";
16 }    
17 }
18 return 0;
19 }

得到的结果是:

1,3,5,7,9,11,13,15,17,19,21,23,25,27,29,31,33,35,37,39,41,43,45,47,49,51,53,55,57,59,61,63,65,67,69,71,73,75,77,79,81,83,85,87,89,91,93,95,97,99,101,103,105,107,109,111,113,115,117,119,121,123,125,127,129,131,133,135,137,139,141,143,145,147,149,151,153,155,157,159,161,163,165,167,169,171,173,175,177,179,181,183,185,187,189,191,193,195,197,199,201,203,205,207,209

继续删去所有3的倍数,

1 #include<iostream>
 2 using namespace std;
 3 int main()
 4 { 
 5 for (int i=1;i<=210;i++)
 6 {
 7     if (i%2==0)
 8 
 9 {
10     i=i;
11 }
12 else if (i%3==0)
13 
14 {
15     i=i;
16 }    
17 
18 else
19 
20 {
21     cout<<i<<",";
22 }
23 }
24 return 0;
25 }

得到

1,5,7,11,13,17,19,23,25,29,31,35,37,41,43,47,49,53,55,59,61,65,67,71,73,77,79,83,85,89,91,95,97,101,103,107,109,113,115,119,121,125,127,131,133,137,139,143,145,149,151,155,157,161,163,167,169,173,175,179,181,185,187,191,193,197,199,203,205,209

继续删去所有5的倍数

1 #include<iostream>
 2 using namespace std;
 3 int main()
 4 { 
 5 for (int i=1;i<=210;i++)
 6 {
 7     if (i%2==0)
 8 
 9 {
10     i=i;
11 }
12 else if (i%3==0)
13 
14 {
15     i=i;
16 }    
17 
18 else if (i%5==0)
19 
20 {
21     i=i;
22 }
23 
24 else
25 
26 {
27     cout<<i<<",";
28 }
29 }
30 return 0;
31 }

得到

1,7,11,13,17,19,23,29,31,37,41,43,47,49,53,59,61,67,71,73,77,79,83,89,91,97,101,103,107,109,113,119,121,127,131,133,137,139,143,149,151,157,161,163,167,169,173,179,181,187,191,193,197,199,203,209

再继续删去所有7的倍数,

1 #include<iostream>
 2 using namespace std;
 3 int main()
 4 { 
 5 for (int i=1;i<=210;i++)
 6 {
 7     if (i%2==0)
 8 
 9 {
10     i=i;
11 }
12 else if (i%3==0)
13 
14 {
15     i=i;
16 }    
17 
18 else if (i%5==0)
19 
20 {
21     i=i;
22 }
23 
24 else if (i%7==0)
25 {
26     i=i;
27 }
28 
29 else
30 
31 {
32     cout<<i<<",";
33 }
34 }
35 return 0;
36 }

得到

1,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,121,127,131,137,139,143,149,151,157,163,167,169,173,179,181,187,191,193,197,199,209

再继续删去所有11的倍数,

1 #include<iostream>
 2 using namespace std;
 3 int main()
 4 { 
 5 for (int i=1;i<=210;i++)
 6 {
 7     if (i%2==0)
 8 
 9 {
10     i=i;
11 }
12 else if (i%3==0)
13 
14 {
15     i=i;
16 }    
17 
18 else if (i%5==0)
19 
20 {
21     i=i;
22 }
23 
24 else if (i%7==0)
25 {
26     i=i;
27 }
28 
29 else if (i%11==0)
30 {
31     i=i;
32 }
33 
34 else
35 
36 {
37     cout<<i<<",";
38 }
39 }
40 return 0;
41 }

得到

1,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,169,173,179,181,191,193,197,199

再删去所有13的倍数,

1 #include<iostream>
 2 using namespace std;
 3 int main()
 4 { 
 5 for (int i=1;i<=210;i++)
 6 {
 7     if (i%2==0)
 8 
 9 {
10     i=i;
11 }
12 else if (i%3==0)
13 
14 {
15     i=i;
16 }    
17 
18 else if (i%5==0)
19 
20 {
21     i=i;
22 }
23 
24 else if (i%7==0)
25 {
26     i=i;
27 }
28 
29 else if (i%11==0)
30 {
31     i=i;
32 }
33 
34 else if (i%13==0)
35 {
36     i=i;
37 }
38 
39 else
40 
41 {
42     cout<<i<<",";
43 }
44 }
45 return 0;
46 }

得到

1,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199

不用再继续下去了,因为$[\sqrt{210}]=14$,即使是再继续下去,那也是做无用功,因为该删去的合数都已经删光了.剩下的都是素数了.

原文链接: https://www.cnblogs.com/yeluqing/archive/2012/12/01/3828041.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍