c++求素数的方法实例与解析。
用c++求100以内的素数
麻烦解释一下以下代码是如何实现求100以内的素数
#include <iostream.h>
#include <math.h>
int main()
{
int i,j,m,sum=0;
for(i=2;i<=100;i++)
{
m=int(sqrt(i));
for(j=2;j<=m;j++)
{
if(i%j==0)break;
}
if(j>m)
{
cout<<i<<"\t";
sum++;
if(sum%5==0)cout<<endl;//输出5个素数就换行一次
}
}
return 0;
2013-08-02 18:42
提问者采纳
for(i=2;i<=100;i++) //因为题目是求100以内的质数，所以检查2至100之间的数据，循环从2到100
{
//以下，是针对每个i进行检查，如果是质数，则输出，否则继续循环，检查下一个数
m=int(sqrt(i)); //对i进行开方，取得i的算术平方根 m
for(j=2;j<=m;j++) //检查2到m中是否有i的因数
{
if(i%j==0)break; //如果检查到有因数则结束j的循环
}
if(j>m) //如果j的循环检查中，没有找到i的因数，则此时j=m+1>m，说明i是质数
{
cout<<i<<"\t";
sum++;
if(sum%5==0)cout<<endl;//输出5个素数就换行一次
}
关于为什么只需要验证到m就可以确定一个数是不是质数，原理如下：
x = a * b ;
a <= 根号x b >=根号x
这个数学原理，想一想就明白了。
- 提问者评价
-
太感谢了
#include
#include int main()
{
int i,j,m,sum=0;
for(i=2;i<=100;i++)
{
m=int(sqrt(i)); //为啥m是i的平方根，其实除到平方根没有整除的，后面就不用除了~
for(j=2;j<=m;j++)//素数的定义知道吧，这个for循环就是判断除了1和自身以外有没有能整除的数字 { if(i%j==0)break; } if(j>m)
{
cout<<i<<”\t”;
sum++;
if(sum%5==0)cout<<endl;//输出5个素数就换行一次
}
}
return 0;
C++使用筛选法求100以内的素数
【问题分析】
我们可以把100个数看作是沙子和石子，素数是石子，非素数的是沙子，弄个筛子，将沙子筛掉，剩下的就是素数。
1至100这些自然数可以分为三类：
(1) 单位数：仅有一个数1.
(2) 素数：这个数大于1，且只有它本身和1这样两个正因数。
(3) 合数：除了1和他自身以外，还有其他的正因数。
【代码如下】
/********************************************************
/* 程 序 名：素数筛选
/* 编程时间：2009年7月27日
/* 主要功能：求素数
*********************************************************/
#include<iostream>
using namespace std;//编译命令
#include<math.h>
const int MAX=100;//定义常量MAX
int main()//主函数
{
int prime[MAX+100]={0};//定义变量并初始化
int i,j,k=sqrt(MAX);
for(i=2; i<=k; i++)//枚举筛数
{
if(prime[i]==0)//如果这个数没被筛，就看看
{
j=i*2;//将原数扩大二倍初始化给j
do
{
prime[j]=1;//将j筛掉
j+=i; //再扩大一倍
}
while(j<=MAX);//直到最大
}
}
for(i=2; i<=MAX; i++)
{
if(prime[i]==0)//循环输出
cout<<i<<” “;
}
cout<<endl;
return 0;//主函数结束
}
【运行结果】
我们可以把100个数看作是沙子和石子，素数是石子，非素数的是沙子，弄个筛子，将沙子筛掉，剩下的就是素数。
1至100这些自然数可以分为三类：
(1) 单位数：仅有一个数1.
(2) 素数：这个数大于1，且只有它本身和1这样两个正因数。
(3) 合数：除了1和他自身以外，还有其他的正因数。
【代码如下】
/********************************************************
/* 程 序 名：素数筛选
/* 编程时间：2009年7月27日
/* 主要功能：求素数
*********************************************************/
#include<iostream>
using namespace std;//编译命令
#include<math.h>
const int MAX=100;//定义常量MAX
int main()//主函数
{
int prime[MAX+100]={0};//定义变量并初始化
int i,j,k=sqrt(MAX);
for(i=2; i<=k; i++)//枚举筛数
{
if(prime[i]==0)//如果这个数没被筛，就看看
{
j=i*2;//将原数扩大二倍初始化给j
do
{
prime[j]=1;//将j筛掉
j+=i; //再扩大一倍
}
while(j<=MAX);//直到最大
}
}
for(i=2; i<=MAX; i++)
{
if(prime[i]==0)//循环输出
cout<<i<<” “;
}
cout<<endl;
return 0;//主函数结束
}
【运行结果】
http://itlab.idcquan.com/Special/QT/Index.html