/**//*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
雪黛依梦 阅读(415)
评论(0) 编辑 收藏 引用 所属分类:
数论