Question

ACM问题 我的代码为什么Runtime error？？ http://poj.org/problem?id=2262

代码：
#include<stdio.h>
#include<algorithm>
#include<time.h>
#include<math.h>
#include<iostream>
using namespace std;

const int MAXSIZE=1000001;
int p[MAXSIZE];
int vis[MAXSIZE];

int prime(int n)
{
int m=sqrt(n+0.5);
int i,j,k,c=0;
memset(vis,0,sizeof(vis));
for(i=2;i<=m;++i)
{
if(!vis[i])
{
p[c++]=i;
}
for(j=i*i;j<=n;j+=i)
{
vis[j]=1;
}
}
for(k=m+1;k<=n;++k)
{
if(!vis[k])
{
p[c++]=k;
}
}
return c;
}
int main()
{
// int t1 = clock();
int num,i,j;
int n=prime(MAXSIZE);
// int t2 = clock();
// printf("\n%d\n",t2 - t1);
while(cin>>num&&num)
{
int sign=0;
for(i=0;i<n;i++)
{
for(j=n-1;j>=0;j--)
{
if(p[i]+p[j]==num)
{
cout<<num<<" = "<<p[i]<<" + "<<p[j]<<endl;
sign=1;
break;
}
}
if(sign==1)
break;
}
if(sign==0)
cout<<"Goldbach's conjecture is wrong."<<endl;
}
return 0;
}

Answer 1

你的prim()函数错误，for(j=i*i;j<=n;j+=i)应该为for(j=2*i;j<n;j+=i)；但是即使这样改了，也是超时的
做了如下改进：
#include<stdio.h>
#include<algorithm>
#include<time.h>
#include<math.h>
#include<iostream>
using namespace std;

const int MAXSIZE=1000001;
int p[MAXSIZE];
bool vis[MAXSIZE];

int prime(int n)
{
int m=sqrt(n+0.5);
int i,j,k,c=0;
memset(vis,0,sizeof(vis));
for(i=2;i<=m;++i)
{
if(!vis[i])
{
p[c++]=i;
}
for(j=2*i;j<n;j+=i)//你的程序在这里越界了
{
vis[j]=1;
}
}
/* for(k=m+1;k<=n;++k)
{
if(!vis[k])
{
p[c++]=k;
}
}*/
return c;
}
int main()
{
// int t1 = clock();
int num,i,j;
int n=prime(MAXSIZE);
// int t2 = clock();
// printf("\n%d\n",t2-t1);
while(cin>>num&&num)
{
int sign=0;
for(i=1;i<n;i++)
{
if(!vis[num-p[i]])//此处去掉一个for循环，直接去vis里找vis[num-p[i]，prim()里面即可省略一个循环
{
cout<<num<<" = "<<p[i]<<" + "<<num-p[i]<<endl;
sign=1;
break;
}
if(sign==1)
break;
}
if(sign==0)
cout<<"Goldbach's conjecture is wrong."<<endl;
}
return 0;
}

Answer 2

Runtime error是运行时错误，一般都是除以0了，或int a[100]，你程序里出现了，i = 101 a[i]了
或i=-2 我想你问题出现在prime(int n)里