什么是素数算法

显示全部楼层 · 2011-4-30 10:53:03

什么是素数算法

千问 · 2011-4-30 10:53:03

素数即只能被1和其本身整除的数，算法判断n是否为素数只需用2~n/2之间的数去除就可以了。因为一个数的一半的平方大于其本身是从5开始的，解方程：n/2的平方n。即一个数n的两个因数不能同时比n/2大。就可以说一个数若不是素数则一定在2~n/2之间有因数。而且2，3也是符合下面程序的。

素数（又称质数）：就是除了1和它本身，没有其他因子的整数。注：1不是素数。

C语言代码算法：
#includestdio.h
main(){
inti,j,k=0;
for(i=2;i=1000;i)
{
for(j=2;j=i/2;j)
if(i%j==0)break;
if(ji/2)
{printf(\"%d\",i);}
}
}