C语言 用筛法求1-1000之间的素数

Question

利用数组放1000个数
挖掉第一个数1（令该数=0）
2没被挖掉，挖掉后面所有2的倍数
3没被挖掉，挖掉后面所有3的倍数
4被挖掉，不执行任何操作
5没被挖掉，挖掉后面所有5的倍数
.......直到最后一个数
剩下的非0数就是素数

Answer 1

1、写我们的头文件和主函数。写好我们的开头。

2、编写定义变量，我们语言定义一个i来用于后面的for循环。

3、输入一个数，在那之前我们要有一个printf()提示一下，显得程序有调理。

4、利用for循环看一看从2到n-1是否能被n整除，如果能就要break。

5、判断素数，如果程序正常结束，就i＞=n，说明他就是素数。

6、如果通过break结束，他就会i<n，所以他就不是素数。

Answer 2

#include <iostream>
using namespace std;
int main()
{
int pre[1002],i,k;
for(i=1;i<1000;i++)pre[i]=i;//填充数字
pre[1]=0;
for(i=1;i<1000;i++)
{
if(pre[i]!=0)//是否被挖
for(k=2;i*k<1000;k++)pre[i*k]=0;//倍数置零
}
for(i=1;i<1000;i++)if(pre[i])cout<<pre[i]<<" ";//输出
return 0;
}

Answer 3

筛选法的规律：(以1~1000内的素数少选为例)
我们知道素数的定义：只能被1和他本身整除的是素数，那这样看的话，只要有一个既不是1又不是这个数本身的数把这个数整除了，就可以说明这个数不是素数了。例如 5是素数，因为5只能被5和1整除，6不是素数，，因为6除了能被1和6整除，还能被2和3整除。试想一下，我们要判断6是不是素数，需不需要循环到6的时候才进行判断呢，不需要，因为2和3都是他的因子，我们在循环到2的时候，找到2的所有倍数，如4，6，8，10，12等等，这些数都至少有2这个因子，因此可以判定它们都不是素数了。而由于4是2的倍数，在循环到2的时候已经判定4不是素数了，所以我们不需要在挖掉4的倍数了，直接跳过4，来到5，挖掉5的所有倍数，然后是6，6在值钱是2的倍数被挖掉了，所以跳过6，来到7.....一直循环到最后一个数字为止，这个时候就是上面7步中说的，剩下没有被挖掉的(挖掉的含义就是把这个数置0)也就是非0的数字就是素数了。
不知道我说的你能不能听懂。希望对你有帮助吧。
#include <stdio.h>
int main()
{
int prime[1002],i,j;
for(i=2;i<1000;i++)
prime[i]=i;//将数组填满1~1000的数字,由于1不是素数，因此我们跳过1，从2开始填
for(i=1;i<1000;i++)
{
if(prime[i]!=0)//是 否已经置0，像4，6，8，10，12等这些数字，在挖2的倍数的时候已经被置零了，所以我们跳过这些数字
for(j=2;i*j<1000;j++)
prime[i*j]=0;//挖掉
}
for(i=1;i<1000;i++)
if(prime[i]!=0)
printf("%d ",prime[i]);//最后非0的数字输出
return 0;
}追问

输出的是一串0啊- -
而且prime[i*j]=0 这个不会给所有的都赋值么？

追答

怎么会呢，我运行正常才给你的，prime[i*j]=0是把i的倍数置0，对于不是i的倍数的整数不会被置0 的。

本回答被提问者采纳