求[a,b]之间所有的素数的个数

发布网友 发布时间：2022-05-13 14:29

我来回答

共4个回答

热心网友 时间：2023-10-12 10:28

改好了。。错误的地方备注了
#include<stdio.h>
#include<math.h>
void main()
{
int a,b,i,k,j,n;
scanf("%d %d",&a,&b);
while((a!=0)&&(b!=0))
{n=0;
for(i=a;i<=b;i++)
{
k=(int)(sqrt(i));
for(j=2;j<=k;j++)
if(i%j==0)
break;
if(j>=k+1) //这里是j>=k+1，并不是i
{
n=n+1;
}

}
printf("%d\n",n); //打印的语句要放到每次判断完一个区间后
scanf("%d%d",&a,&b);
}
}

热心网友 时间：2023-10-12 10:28

以下为所知道的可以满足LZ要求的算法.

-------------------------------------------------------------------------------------------------------
2.b sieve筛选法求一段区间内的素数
-------------------------------------------------------------------------------------------------------
/*
*sieve筛选法求一段区间内素数
*maxn -区间最大长度
*L -区间左边界
*U -区间右边界
*p[] -保存区间内素数
*flag[] -表示区间内某个数是否是素数,i-L查询
*sz -区间内素数个数
*/
/*
*sieve筛选法求一段区间内素数
*maxn -区间最大长度
*L -区间左边界
*U -区间右边界
*p[] -保存区间内素数
*flag[] -表示区间内某个数是否是素数,i-L查询
*sz -区间内素数个数
*/
#define maxn 1024000
int L,U;
int p[maxn],sz;
bool flag[maxn];
void sieve(int L,int U){
int d=U-L+1,i,limit=(int)sqrt((double)U);
for(i=0;i<d;i++)flag[i]=true;
for(i=L&0x1;i<d;i+=2)flag[i]=false;
for(i=3;i<=limit;i+=2){
if(i>L&&flag[i-L]==false)continue;
int j=L/i*i;
if(j<L)j+=i;
if(j==i)j+=i;
j=j-L;
for(;j<d;j+=i)flag[j]=false;
}
if(L<=1)flag[1-L]=false;
if(L<=2)flag[2-L]=true;
sz=0;
for(i=0;i<d;i++)if(flag[i]==true)p[sz++]=i+L;
}

热心网友 时间：2023-10-12 10:29

最好把判断素数作为一个函数...

热心网友 时间：2023-10-12 10:29

//---------------------------------------------------------------------------

#include<stdio.h>
#include<math.h>
void main()
{
int a,b,i,k,j,n;
scanf("%d %d",&a,&b);
while((a!=0)&&(b!=0))
{n=0;
for(i=a;i<=b;i++)
{
k=(int)(sqrt(i));
for(j=2;j<=k;j++)
if(i%j==0)
break;
if(j>=k+1) /*注意这里*/
{
n=n+1;
}

}
printf("%d\n",n); /*注意这里*/
scanf("%d%d",&a,&b);
}
}
//---------------------------------------------------------------------------