結果

問題 No.36 素数が嫌い！
ユーザー koba-e964koba-e964
提出日時 2015-05-13 13:17:56
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 2,393 bytes
コンパイル時間 1,415 ms
コンパイル使用メモリ 158,128 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-07-06 01:21:58
合計ジャッジ時間 2,179 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 2 ms
6,944 KB
testcase_02 AC 2 ms
6,940 KB
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 AC 1 ms
6,940 KB
testcase_08 AC 2 ms
6,944 KB
testcase_09 AC 2 ms
6,944 KB
testcase_10 AC 2 ms
6,944 KB
testcase_11 WA -
testcase_12 WA -
testcase_13 AC 2 ms
6,944 KB
testcase_14 AC 1 ms
6,944 KB
testcase_15 AC 2 ms
6,940 KB
testcase_16 AC 2 ms
6,944 KB
testcase_17 AC 2 ms
6,940 KB
testcase_18 AC 2 ms
6,940 KB
testcase_19 AC 2 ms
6,940 KB
testcase_20 WA -
testcase_21 AC 1 ms
6,940 KB
testcase_22 WA -
testcase_23 AC 1 ms
6,944 KB
testcase_24 AC 1 ms
6,944 KB
testcase_25 AC 1 ms
6,944 KB
testcase_26 WA -
testcase_27 WA -
testcase_28 WA -
testcase_29 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

/*
 * This implementation is based on the paper (http://ceur-ws.org/Vol-1326/020-Forisek.pdf).
 */

__uint16_t bases[] = {
  15591,2018,166,7429,8064,16045,10503,4399,1949,1295,2776,3620,560,3128,5212,
  2657,2300,2021,4652,1471,9336,4018,2398,20462,10277,8028,2213,6219,620,3763,4852,5012,3185,
  1333,6227,5298,1074,2391,5113,7061,803,1269,3875,422,751,580,4729,10239,746,2951,556,2206,
  3778,481,1522,3476,481,2487,3266,5633,488,3373,6441,3344,17,15105,1490,4154,2036,1882,1813,
  467,3307,14042,6371,658,1005,903,737,1887,7447,1888,2848,1784,7559,3400,951,13969,4304,177,41,
  19875,3110,13221,8726,571,7043,6943,1199,352,6435,165,1169,3315,978,233,3003,2562,2994,10587,
  10030,2377,1902,5354,4447,1555,263,27027,2283,305,669,1912,601,6186,429,1930,14873,1784,1661,
  524,3577,236,2360,6146,2850,55637,1753,4178,8466,222,2579,2743,2031,2226,2276,374,2132,813,
  23788,1610,4422,5159,1725,3597,3366,14336,579,165,1375,10018,12616,9816,1371,536,1867,10864,
  857,2206,5788,434,8085,17618,727,3639,1595,4944,2129,2029,8195,8344,6232,9183,8126,1870,3296,
  7455,8947,25017,541,19115,368,566,5674,411,522,1027,8215,2050,6544,10049,614,774,2333,3007,
  35201,4706,1152,1785,1028,1540,3743,493,4474,2521,26845,8354,864,18915,5465,2447,42,4511,
  1660,166,1249,6259,2553,304,272,7286,73,6554,899,2816,5197,13330,7054,2818,3199,811,922,350,
  7514,4452,3449,2663,4708,418,1621,1171,3471,88,11345,412,1559,194};

typedef __uint32_t uint32_t;
typedef __uint64_t uint64_t;

bool is_SPRP(uint32_t n, uint32_t a) {
  uint32_t d = n - 1, s = 0;
  while ((d&1) == 0) {
    ++s; d >>= 1;
  }
  uint64_t cur = 1, pw = d;
  while (pw) {
    if (pw & 1) {
      cur = (cur*a) % n;
    }
    a = ((uint64_t)a*a) % n;
    pw >>= 1;
  }
  if (cur == 1) {
    return true;
  }
  for (uint32_t r=0; r<s; r++) {
    if (cur == n-1) {
      return true;
    }
    cur = (cur*cur) % n;
  }
  return false;
}
bool is_prime(uint32_t x) {
  if (x==2 || x==3 || x==5 || x==7) {
    return true;
  }
  if (x%2==0 || x%3==0 || x%5==0 || x%7==0) {
    return false;
  }
  if (x < 121) {
    return x > 1;
  }
  uint64_t h = x;
  h = ((h >> 16) ^ h) * 0x45d9f3b;
  h = ((h >> 16) ^ h) * 0x45d9f3b;
  h = ((h >> 16) ^ h) & 255;
  return is_SPRP(x,bases[h]);
}

int main(){
long long n;cin>>n;
if(n == 1 || is_prime(n) == true) {
  cout << "NO"<<endl;
}else cout<<"YES"<<endl;
}
0