HDU--1397

原题地址
一道关于素数的水题，可以直接用板子。
记录一下自己的犯傻经历。需要自己反思的事情就是 ， 自己对板子理解不够深彻 ， 欧拉筛法用了两个数组来判断是否是素数 ， 然而自己直盯着那个存了素数的数组， 没有关注那个按顺序排的vis数组（bool的那个），其实只要判断这个bool的数组是否在相应位置是true就可以了 ， 自己非要用双重for超时好多发。。。
这个是超时的代码：

#include<iostream>
#include<string>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<set>
#include<cstring>
using namespace std;
const int Max = 100020;
int Prime[Max];
bool vis[Max];
void prepare()
{
    int num = 0;
    memset(vis,1,sizeof(vis));
    for(int i = 2; i <= Max; ++i)
    {
        if(vis[i])
            Prime[++num] = i;
        for(int j = 1; j <= num; ++j)
        {
            if (i * Prime[j] > Max)
                break;
            vis[i * Prime[j]] = false;
            if (i % Prime[j] == 0)
                break;
        }
    }
}
int main()
{
    int n;
    prepare();
    while(cin >>n)
    {
        if(n==0)
        {
            break;
        }
        int numa=0;
        for(int i=1;Prime[i]<n;i++){
            for(int j=i;Prime[j]<n;j++){
                if(Prime[i]+Prime[j]==n){
                    numa++;
                }
            }
        }
        //cout<<Prime[1]<<endl;
        printf("%d\n", numa);
    }
    return 0;
}

这个是AC的代码：

#include<iostream>
#include<string>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<set>
#include<cstring>
using namespace std;
const int Max = 100020;
int Prime[Max];
bool vis[Max];
void prepare()
{
    int num = 0;
    memset(vis,1,sizeof(vis));
    vis[0] =0;
    vis[1] =0;
    for(int i = 2; i <= Max; ++i)
    {
        if(vis[i])
            Prime[++num] = i;
        for(int j = 1; j <= num; ++j)
        {
            if (i * Prime[j] > Max)
                break;
            vis[i * Prime[j]] = false;
            if (i % Prime[j] == 0)
                break;
        }
    }
}
int main()
{
    int n;
    prepare();
    while(cin >>n)
    {
        if(n==0)
        {
            break;
        }
        int numa=0;
        for(int i=2;i<=n/2;i++){
                if(vis[i]&&vis[n-i]){
                    numa++;
            }
        }
        //cout<<Prime[1]<<endl;
        printf("%d\n", numa);
    }
    return 0;
}