1006. Prime

超时

超时

Time Exceeded King
[em:15]

在？为什么WA?

include

using namespace std;
vector primes(1000005, true);
void init(){
primes[1] = false;
for(int i = 2; i * i <= 1000005; i++){
if(primes[i]){
for(int j = 2; j * i <= 1000005; j++)primes[j * i] = false;
}
}
}
int main(){
int n, m;
init();
while(scanf(“%d%d”, &n, &m) != EOF){
int ans = 0;
for(int i = n; i <= m; i++){
if(primes[i])ans++;
}
printf(“%d\n”, ans);
}
return 0;
}

超时

include

using namespace std;

int prime(int N,int M);
bool isPrime(int X);

int main(){
int N,M;
int num;
cin>>N>>M;
num=prime(N,M);
cout<<num<<endl;
return 0;
}

int prime(int N,int M){
int count=0;
for(int i=N;i<M;i++){
if(isPrime(i)==true)
count++;
}
return count;
}

bool isPrime(int X){
bool flag=true;
for(int i=2;i<X;i++){
if(X%i==0)
flag=false;
}
return flag;
}
c++…我觉得没问题啊，但是是WA..什么情况

不知道怎么回事？为什么是WA？

include

int main()
{
int n,m,x,y;
while(scanf(“%d %d”,&x,&y)!=EOF)
{
n=y;m=0;
int a[100001],i,j,z;
for(i=2;i<=n;i++)
a[i]=i;
for(i=2;i<=n;i++)
{
if(a[i]!=0)
for(j=i+i;j<=n;j+=i)
a[j]=0;
}

for(i=2;i<=n;i++)
{if(a[i]!=0&&a[i]>=x&&a[i]<=y)
m++;
}
printf(“%d\n”,m);
}
}

这个题要用埃氏筛！！！纪念一下！！！（Python3）

try:
    is_prime = [1] * 1000000
    prime = {0:0, 1:0}
    count = 0
    for i in range(2, 1000000):
        if is_prime[i]:
            count += 1
            for j in range(i*i, 1000000, i):
                is_prime[j] = 0
        prime[i] = count

    while True:
        n, m = [int(i) for i in input().split()]
        print(prime[m] - prime[n-1])

except:
    pass

oh，是我理解错了

这题有问题，Prime number里没有1。