2007年アジア予選B問題（Prime Gap）(2007/11/15(木) 00:49:27)

2007年アジア予選B問題を解いてみた

解法

エラトステネスの篩で素数配列を生成し、素数以外の数字なら素数間の距離を数えて出力するだけ。

ソース

（目標10分以内）

#include 
#include 
using namespace std;

#define MAX_LEN 1299800//>1299709

int main(){
    char table[MAX_LEN];

    memset(table, 1, sizeof(char) * MAX_LEN);
    table[0] = table[1] = 0;
    for(int i = 2;;i++){
        while(table[i] == 0 && i <= sqrt(MAX_LEN))i++;
        if(i > sqrt(MAX_LEN))break;
        for(int j = i + 1; j < MAX_LEN; j++){
            if(j % i == 0)table[j] = 0;
        }
    }

    int n;
    while(cin >> n, (n)){
        if(table[n] == 1)cout << 0 << endl;
        else{
            while(table[--n] == 0);
            int i;
            for(i = 1; table[i + n] == 0; i++);
            cout << i << endl;
        }
    }

    return 0;
}