如何写一个求n-m之间的全部素数的程序
发布网友
发布时间：2022-07-24 08:56
共4个回答
热心网友
时间：2023-10-08 23:18
#include <iostream>
using namespace std;
#include <math.h> //此为数学函数库。程序中要用到数学函数时必须包含此语句。
int f(int n) //此函数只判断是否为素数。
{
int i,j=0;
for(i=2;i<=sqrt(n);i++) //这是使程序运算次数最少的方法，若将sqrt(n)换成n/2，
//程序运算次数将要增加,若换成n，运算量最大，也最浪费。
//另外，若i=1，显然不满足，故直接i=2。
if(n%i==0)
j++; //j在这里只起标识作用，若为0不变则说明是素数，否则为非素数。
if(j==0)
return 1;
else
return 0;
}
int main()
{
int i,n,m;
cout<<"请输入正整数n和m（0<n<m）:"<<endl;
cin>>n>>m;
cout<<n<<"到"<<m<<"之间的素数为："<<endl;
for (i=n;i<=m;i++)
{
if(f(i))
{
cout<<i<<" ";
}
}
cout<<endl;
return 0;
}
热心网友
时间：2023-10-08 23:19
using namespace std;
int main()
{
int a[210000];
int i,j,m,n;
cout<<"please input the range: m,n"<<endl;
cin>>m>>n;
for (i=1;i<=n;i++)
a[i]=0;
i=2;
while (i<=n/2+1)
{
if (!a[i])
{
for (j=2;j<=n/i+1;j++)
{
if (i*j<=n) a[i*j]=1;
//将素数i的倍数都标记成合数；
//当a[x]=1时，x为合数；a[x]=0表示x为素数或未判断。
}
}
i++;
while (a[i]) i++;
//移动指针到下一个素数。
}
for (i=m;i<=n;i++)
{
if (!a[i])
//当a[x]=1时，x为合数；a[x]=0表示x为素数。
{
cout<<i<<' ';
}
}
return 0;
}
/*
筛选法求素数：
①将所有候选数放入筛中；（数组a）
②找筛中最小数（必为素数）i；
③将next的所有倍数从筛中筛去；
④重复②～④直到筛空。
如果按照基本方法，对每一个数m，把i从2到sqrt（m）+1来判断i是否是m的约数，最后判断m是否素数的话，当数据到200000的时候，仅处理（仅判断而不输出)就需要5s以上的时间，而采用了筛选法，数据量在200000的时候，不输出的话可以实现秒出。
*/
热心网友
时间：2023-10-08 23:19
input n,m
for i= n to m
for k=2 to sqr(i)
if i mod k=0 then print i
next k
next i
参考资料：我也是干这一行的！
热心网友
时间：2023-10-08 23:20
