回复 8楼 九转星河
我的算法不对
回复 5楼 九转星河
拖延症晚期来报道:/* 按照我之前的思路做,只能先求出1~a之间的素数个数,再求出1~b之间的素数个数,然后将两者相减得到结果,这样做将1~a之间的过程
重复计算了两次,不是很好
换一种思路是利用筛法先将所有素数球出来,然后再判断a~b之间有多少个素数
*/
第一种求法:
#include <stdio.h>
#include <math.h>
int c[1000001];
int main()
{
int K,i,j,t;//k是案例个数
int a,b;
scanf("%d",&K);
//输入a和b的值
while(K--)
{
//用筛法把非素数都赋值成0.
int t,num1=0,num2=0;
scanf("%d %d",&a,&b);
for(i=2; i<=a; i++)//对数组进行初始化
{
c[i] = i;
}
for(i=2; i<=sqrt(a); i++)//进行筛选
{
for(j=i+1; j<=a; j++)
{
if(c[i]!=0 && c[j]!=0 && c[j]%c[i]==0)
{
c[j]=0;
}
}
}
for(i=2; i<=a; i++)
{
if(c[i]!=0)
{
num1++;
}
}
for(i=2; i<=b; i++)//对数组进行初始化
{
c[i] = i;
}
for(i=2; i<=sqrt(b); i++)//进行筛选
{
for(j=i+1; j<=b; j++)
{
if(c[i]!=0 && c[j]!=0 && c[j]%c[i]==0)
{
c[j]=0;
}
}
}
for(i=2; i<=b; i++)
{
if(c[i]!=0)
{
num2++;
}
}
if(num1>num2)
{
t=num1;
num1=num2;
num2=t;
}
printf("%d\n",num2-num1+1);
}
return 0;
}
第二种求法:
#include <stdio.h>
#define N 1000001
int prime[N];
int main()
{
int K,i,c;
scanf("%d",&K);
for(i=2;i<N;i++) //筛法求素数
{
prime[i]=1;
}
prime[0]=prime[1]=0;
for(i=2;i<=1000;i++)
{
if(prime[i])
{
for(c=i*i;c<=N;c+=i)
{
prime[c]=0;
}
}
}
while(K--)
{
int t,a,b,num=0;
scanf("%d %d",&a,&b); //输入a b的值,如果a>b则将a与b的值交换
if(a>b)
{
t=a;
a=b;
b=t;
}
for(i=a;i<=b;i++) //ab之间有多少个素数
{
if(prime[i]==1)
{
num++;
}
}
printf("%d\n",num);
}
return 0;
}
测试没问题了,不过我在网站提交还是显示time limit exceed 没有ac还是要继续改