滴水逆向联盟

标题: 基于visual Studio2013解决C语言竞赛题之0507筛选素数 [打印本页]

---

作者: 大灰狼    时间: 2014-9-23 07:26
标题: 基于visual Studio2013解决C语言竞赛题之0507筛选素数
题目

解决代码及点评

• <pre code_snippet_id="91880" snippet_file_name="blog_20131202_1_2646179" class="cpp" name="code"></pre><pre code_snippet_id="91880" snippet_file_name="blog_20131202_1_2646179" class="cpp" name="code"><pre code_snippet_id="91880" snippet_file_name="blog_20131202_1_2646179" class="cpp" name="code">/************************************************************************/  
• /*  
• 7．  用筛选法求 2到 100之间的素数。
• 方法如下：首先 2是素数，凡 2 的倍数都不是素数，于是把这些数从数表中筛去，  
• 2以后没有被筛去的第一个数是 3， 然后把 3的倍数都从数表中筛去， 3以后没被筛去的第一个数是 5
• ，然后把 5 的倍数都从数表中筛去。如此下去，直到遇到某数 K（≤ N），其后没有数可筛选为止，  
• 这时保留下的未被筛去的数就是 2到 N的素数。
• */  
• /************************************************************************/  
• #include <stdio.h>  
• #include <stdlib.h>  
• #include <math.h>  
•   
•   
•   
• void main()  
• {  
•     const int N=101;  
•     int Sn=(int)sqrt(double(N-1)); // 筛选法只要筛选到sqrt(N-1)  
•     int arr[N]; // N个标记，如果arr[k] = 1表示k是素数  
•     for (int i=0;i<N;i++)  
•     {  
•         arr=1; // 初始化时认为全是素数  
•     }  
•     arr[0]=arr[1]=0; // 0和1认为不是素数  
•     for (int j=2;j<Sn;j++) // 从2开始循环  
•     {       // 如果j对应的值是0，那么j是合数，则找下一个  
•         while (arr[j]==0)//循环取得数字  
•         {  
•             j++;  
•         }  
•         for (int i=j+j;i<N;i=i+j)//找到某个素数之后，把它倍数下标对应的值改成0，表示合数  
•         {  
•   
•             arr=0;  
•   
•         }  
•     }  
•     for (int i=2;i<N;i++) // 输出下标为1的素数  
•     {  
•         if (arr==1)  
•         {  
•             printf("%5d",i);  
•         }  
•     }  
•   
•   
•     system("pause");  
• }</pre><br><br></pre>  
  

---

欢迎光临 滴水逆向联盟 (http://www.dtdebug.com/)

Powered by Discuz! X3.2