Question

ACM问题 我的代码那些数据过不了？？？http://acm.swjtu.edu.cn/JudgeOnline/showproblem?problem_id=1381

我的代码：
#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<stdlib.h>
#include<memory.h>
#include<math.h>
using namespace std;
const int MAXSIZE=100100;
int p[MAXSIZE];
int vis[MAXSIZE];
int prime(int n)
{
int i,j,k=0;
int s,e=(int)(sqrt(0.0+n)+1);
memset(vis,1,sizeof(vis));
p[k++]=2;
vis[0]=vis[1]=0;
for(i=4;i<n;i+=2)
vis[i]=0;
for(i=3;i<e;i++)
{
if(vis[i])
{
p[k++]=i;
for(s=i*2,j=i*i;j<n;j+=s)
vis[j]=0;
}
}
for(;i<n;i+=2)
if(vis[i])
p[k++]=i;
return k;
}
int main()
{
int n,i,count,sum;
int a[1001];
int t=100050;
count=prime(t);
cout<<"Primes found between 2 and 20: 8"<<endl;
cout<<"Interprime Gap Frequency"<<endl;
while(cin>>n)
{
sum=0;
memset(a,0,sizeof(a));
for(i=0;p[i]<n;i++)
{
sum++;
if(i>0&&p[i]<n)
a[p[i]-p[i-1]]++;
}
cout<<"Primes found between 2 and "<<n<<": "<<sum<<endl
<<endl<<"Interprime Gap Frequency"<<endl;
for(i=0;i<1001;i++)
{
if(a[i]!=0)
printf("%8d%15d\n",i,a[i]);
}
}
return 0;
}

Answer 1

#include <iostream>
#include <CMATH>
using namespace std;
const int N=500001;
bool is[N*2]; int prm[N];
int getprm(int n){
int i, j, k = 0;
int s, e = (int)(sqrt(0.0 + n) + 1);
memset(is, 1, sizeof(is));
is[0] = is[1] = 0;
for (i = 4; i < n; i += 2) is[i] = 0;
for (i = 3; i < e; i += 2) if (is[i]) {
for (s = i * 2, j = i * i; j < n; j += s)
is[j] = 0;
}

return 0;
}
int main()
{
int n,i;
getprm(100003);

while(scanf("%d",&n)!=EOF)
{
memset(prm,0,sizeof(prm));

int now=2;
int Max=0;
int num=1;
for(i=3;i<=n;i++)
{
if(is[i])
{
num++;
if(i-now>Max)
Max=i-now;
prm[i-now]++;
now=i;
}
}
printf("Primes found between 2 and %d: %d\n\n",n,num);
printf("Interprime Gap Frequency\n");
for(i=1;i<=Max;i++)
{
if(prm[i]!=0)
printf("%8d%15d\n",i,prm[i]);
}
printf("\n");

}
return 0;
}