求100内的质数，第一次写c++的程序，请大家多指教

abid 发布于 2007-09-20 17:28， 1970 次点击

#include "stdafx.h"

int main(int argc, char* argv[])
{
int x=100;

for(int j=1;j<x;j++){

int y=0;
for(int i=2;i<j;i++){

if(j%i==0){
y++;
}

if(y>0){
// printf("%d\n",j);
break;
}

}

if(y==0){
printf("%d\n",j);
}

}

return 0;
}

9 回复

yushui2007-09-20 20:06

还是C的啊

aipb20072007-09-20 21:53

可以再简化的哦，2的个循环里只需要到j^1/2（j开方）

yuyunliuhen2007-09-20 22:10

也可以用筛选法

for(i=1;i<=100;i++) //循环赋值a[i]
a[i]=i;
for(i=2;i<sqrt(100);i++)
for(j=i+1;j<=100;j++)
{
if(a[i]!=0&&a[j]!=0)
if(a[j]%a[i]==0) //[j]能被a[i]整除
a[j]=0; //使a数组中所有是a[j]的倍数的数组元素a[j]=0
}

for(i=2,n=0;i<=100;i++)
{
if(a[i]!=0)
{
cout<<a[i]<<" ";
n++;
}
}

天下第二刀2007-09-20 23:12

楼上不错

[此贴子已经被作者于2007-9-20 23:13:05编辑过]

kisscjy2007-09-20 23:40

4楼厉害,学到东西了~~

野比2007-09-22 12:17

当a不是质数，那么a*N也不是质数，a*N就可以不加处理直接忽略……

nuciewth2007-09-22 13:27

筛选法效率很快,但空间需求很大.
1000之内不必把这搬上来的.
直接做判断就行了.
k=1;a[0]=2;
for(i=3;i<=1000;i+=2)
{
for(j=2;j*j<=i;j++)
{
if(i%j==0)break ;
}
if(j*j>i)a[k++]=i;
}

绿茶2007-09-22 23:09

不错

#10

风致2007-09-23 01:45

呵呵，有点难理解，看的不大懂，算法不错！