結果

問題 No.843 Triple Primes
コンテスト
ユーザー shoshosho
提出日時 2020-02-14 19:50:40
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 3 ms / 2,000 ms
コード長 1,016 bytes
コンパイル時間 1,479 ms
コンパイル使用メモリ 166,404 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-10-06 09:47:30
合計ジャッジ時間 2,494 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 42
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include "bits/stdc++.h"

using namespace std;
typedef long long ll;
typedef long double lb;
#define rep(i,j,n) for (ll i = j; i < (n); i++)
#define CLR(mat,f) memset(mat, f, sizeof(mat))
#define IN(a, b, x) (a<=x&&x<b)
#define out(ans) cout << ans << endl
typedef pair<ll,ll>P;
const ll mod=1e9+7;
const int INF = 1000000;
const double PI=3.14159265359;

int main(){

  ll n;cin>>n;

  bool is_prime[n+1];CLR(is_prime,true);
  is_prime[0]=false;
  is_prime[1]=false;

  // vector<ll>prime;
  for(ll i=2;i*i<=n;i++){
    if(is_prime[i]){
      // prime.push_back(i);
      for(ll j=2;i*j<=n;j++){
        is_prime[i*j]=false;
      }
    }
  }
  // for(auto p:prime){
  //   out(p);
  // }
  ll ans=0;
  // out(prime[prime.size()-1]);
  for(ll i=2;i*i-2<=n;i++){
    if(is_prime[i]&&is_prime[i*i-2]){
      ans++;
      if(i!=2){
          ans++;
      }
    }
  }
  out(ans);
  // ll ans=0;
  // rep(i,0,prime.size()){
  //   rep(j,i,prime.size()){
  //     if(prime[i]+prime[j]==)
  //   }
  // }



  return 0;
}
0