結果

問題 No.843 Triple Primes
ユーザー face4
提出日時 2019-06-28 21:51:07
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 46 ms / 2,000 ms
コード長 622 bytes
コンパイル時間 683 ms
コンパイル使用メモリ 75,484 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-09-19 14:00:16
合計ジャッジ時間 2,961 ms
ジャッジサーバーID
(参考情報)
judge5 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 2
other AC * 42
権限があれば一括ダウンロードができます

ソースコード

diff #

#include<iostream>
#include<vector>
#include<map>
using namespace std;

int main(){
    vector<int> p;
    bool nonp[500001] = {};
    nonp[0] = nonp[1] = true;
    for(int i = 2; i < 500001; i++){
        if(nonp[i]) continue;
        p.push_back(i);
        for(int j = i+i; j < 500001; j += i)  nonp[j] = true;
    }

    int n;
    cin >> n;

    // 2.5e8 ??
    int ans = 0;
    for(int i = 0; i < p.size() && p[i] <= 1000; i++){
        int x = p[i]*p[i];
        for(int j = 2; j <= n && x-j >= j; j++)   if(x-j <= n && !nonp[j]&&!nonp[x-j])   ans+=(j==x-j ? 1 : 2);
    }

    cout << ans << endl;

    return 0;
}
0