/**//*1.樸素法 只適合 N 很小的時候 復(fù)雜度：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.最簡單的素?cái)?shù)衰選法:思路：因?yàn)榕紨?shù)不可能是素?cái)?shù)，而且第一個奇數(shù)是素?cái)?shù)，
//故定義一個prime數(shù)組，將其下標(biāo)為偶的初始化為flase，而下表為奇的初始化true，并且奇數(shù)的偶數(shù)倍false
//輸出 0-100內(nèi)的素?cái)?shù)
//缺點(diǎn)： 奇數(shù)的倍數(shù)賦為false 時，出現(xiàn)了同一個多次標(biāo)記；如：3 5 的倍數(shù) 15 被兩次標(biāo)記
#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++)//將奇數(shù)的倍數(shù)賦為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篩法:得到一個新的素?cái)?shù)后將它的倍數(shù)剔除掉
//缺點(diǎn)：剔除素?cái)?shù)的倍數(shù)時，出現(xiàn)了同一個多次標(biāo)記：如 2 3 的倍數(shù) 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] ) //是素?cái)?shù)
{
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篩選素?cái)?shù)的方法：同樣的思路避免了上述的缺點(diǎn)
//理解這種機(jī)制
#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; //最多標(biāo)記到本身的倍數(shù)，而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
雪黛依夢 閱讀(433)
評論(0) 編輯 收藏 引用 所屬分類:
數(shù)論