/**//*1.樸素法 只適合 N 很小的時候 復雜度：n * sprt(n)
#include <stdio.h>
#include <stdlib.h>
int main ()
{
int N;
scanf ("%d", &N);
int j,i ;
for ( i = 2; i <= N; i ++) //i
{
for ( j = 2; j*j <= i; j++ )// j <= 根號i
{
if ( i % j == 0 )
break;
}
if ( j*j > i )
printf ("%d ",i);
}
system("pause");
return 0;
}*/
/**//*2.最簡單的素數衰選法:思路：因為偶數不可能是素數，而且第一個奇數是素數，
//故定義一個prime數組，將其下標為偶的初始化為flase，而下表為奇的初始化true，并且奇數的偶數倍false
//輸出 0-100內的素數
//缺點： 奇數的倍數賦為false 時，出現了同一個多次標記；如：3 5 的倍數 15 被兩次標記
#include <stdio.h>
#include <stdlib.h>
int main ()
{
bool prime[101];
int i, j, k;
for ( i = 0; i < 101; i++)
{
if ( i % 2== 0)
prime[i] = false;
else
prime[i] = true;
}
prime[2] = true;prime[1] = false;//特例處理
for ( j = 3; j < 101; j++)//將奇數的倍數賦為false
{
if ( prime[j] == true )
{
for (int m = 2*j; m < 101; m+=j)
{
prime[m] = false;
}
}
}
for ( k = 0; k < 101; k ++)
{
if (prime[k]==true)
printf ("%d ", k);
}
system("pause");
return 0;
}*/
/**//*3.Eraosthenes篩法:得到一個新的素數后將它的倍數剔除掉
//缺點：剔除素數的倍數時，出現了同一個多次標記：如 2 3 的倍數 6 12
#include <stdio.h>
#include <stdlib.h>
int main ()
{
static int prime[101];
prime[0] = 1; prime[1] = 1;
int i , j;
for ( i = 2; i < 101; i ++)
{
if ( ! prime[i] ) //是素數
{
for (j = 2*i; j < 101; j+=i)
{
prime[j] = 1;
}
}
}
for (int m = 2; m < 101; m++)
{
if ( !prime[m] )
printf ("%d ",m);
}
system("pause");
return 0;
}*/
//線性Eraosthenes篩選素數的方法：同樣的思路避免了上述的缺點
//理解這種機制
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 1000
int tag[MAXSIZE + 1];
int main ()
{
int prime[MAXSIZE];
int i, j;
int cn = 0;
for (i = 2; i< MAXSIZE + 1; i ++)
{
if ( !tag[i] )
prime[cn++] = i;
for ( j = 0; (j < cn) && (prime[j] * i < MAXSIZE + 1) ; j++ )
{
tag[ i * prime[j] ] = 1; //最多標記到本身的倍數，而prime【j】的最大恰好為 i ，而 最大時 j = cn；
if ( i % prime[j] == 0 )
break;
}
}
printf ("%d\n", cn);
for (int m = 0; m < cn; m ++)
{
printf ("%d ",prime[m]);
}
printf ("\n");
system("pause");
return 0;
}
posted on 2010-08-28 21:32
雪黛依夢 閱讀(432)
評論(0) 編輯 收藏 引用 所屬分類:
數論