斑的家

這題就是找prime 的變形題，prime 大到快20000000，千萬等級，

但還好篩法還夠快。

#include<iostream>
#include<vector>
#define SIZE 20000001
using namespace std;
/*
 *    AUTHOR : benbendog
 *    DATE   : 2010/12/21
 *   PROBLEM : find the n-th twin primes (p,p+2), both are primes
 *   SOLUTION: use sieve to find primes within 20000000
 *             it takes about 1~2s to do that.
 *             then the rest is trivial.
 */
struct twin
{
    twin(){}
    twin(int x,int y):a(x),b(y){}
    int a,b;
};
vector<twin> v;
bool p[SIZE];
void init();
int main()
{
    int n;
    init();
    while(cin>>n)
    {
        --n;
        cout<<"("<<v[n].a<<", "<<v[n].b<<")"<<endl;
    }
    return 0;
}
void init()
{
    memset(p,true,sizeof(p));
    p[1] = p[0]= false;
    for(int i = 2 ; i< SIZE;i++)
    {
        if(!p[i])continue;
        for(int j = 2*i ; j<SIZE;j+=i)
            p[j]=false;
    }
    for(int i = 3 ; i < SIZE-2;i++)
    {
        if(p[i] && p[i+2])v.push_back(twin(i,i+2));
    }
}