求素数的几种方法

﹏ヽ暗。殇╰゛Y 2022-05-28 00:35 125阅读 0赞

# 求素数的几种方法 #

一，普通方法

C++ Code

二，筛选法求

C++ Code

<table style="font-family:Consolas, 'Courier New';font-size:12px;vertical-align:text-top;line-height:15px;"> 
 <tbody> 
 <tr> 
 <td style="color:#008284;background-color:#e3e3e3;vertical-align:text-top;"> 
 <div style="margin:7px;text-align:right;white-space:nowrap;">
 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 
 
 </div></td> 
 <td style="background-color:#008284;padding:1px;"> 
 <div style="border:1px #008284 solid;"></div></td> 
 <td style="background-color:#efefef;width:100%;vertical-align:text-top;color:#000000;"> 
 <div style="margin:7px;"> 
 #include&lt;stdio.h&gt; 
 
 #include&lt;math.h&gt; 
 
 #define&nbsp;N&nbsp; 
 10000001 
 
 bool&nbsp;prime[N]; 
 
 int&nbsp;main() 
 
 { 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 int&nbsp;i,&nbsp;j; 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 for(i&nbsp;=&nbsp; 
 2;&nbsp;i&nbsp;&lt;&nbsp;N;&nbsp;i++) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 if(i&nbsp;%&nbsp; 
 2) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;prime[i]&nbsp;=&nbsp; 
 true; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 else 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;prime[i]&nbsp;=&nbsp; 
 false; 
 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 for(i&nbsp;=&nbsp; 
 3;&nbsp;i&nbsp;&lt;=&nbsp;sqrt(N);&nbsp;i++) 
 &nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 if(prime[i]) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 for(j&nbsp;=&nbsp;i&nbsp;+&nbsp;i;&nbsp;j&nbsp;&lt;&nbsp;N;&nbsp;j&nbsp;+=&nbsp;i) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;prime[i]&nbsp;=&nbsp; 
 false; 
 &nbsp;&nbsp;&nbsp;&nbsp;} 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 for(i&nbsp;=&nbsp; 
 2;&nbsp;i&nbsp;&lt;&nbsp; 
 100;&nbsp;i++) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 if(&nbsp;prime[i]&nbsp;) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;printf( 
 "%d&nbsp;",&nbsp;i); 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 return&nbsp; 
 0; 
 
 } 
 
 </div></td> 
 </tr> 
 </tbody> 
</table>