結果

問題 No.36 素数が嫌い！
ユーザー MaxMellonMaxMellon
提出日時 2015-10-05 22:52:40
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 1,492 bytes
コンパイル時間 402 ms
コンパイル使用メモリ 55,800 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-20 01:12:58
合計ジャッジ時間 1,288 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#include <iostream>
using namespace std;

class Math
{
private:

public:
  static int calcPowMod(int x, int n, int mod);
  static bool isPrime(unsigned long n);
  static int countPrime(int max);
};

/**
 * calcPowMod
 * x^n % mod の 計算結果を返します
 * (二分累乗法)
 **/
int Math::calcPowMod(int x, int n, int mod)
{
  unsigned long sum;
  if ( n == 0 ) { return 1; }
  if ( n == 1 ) { return x % mod; }
  sum = Math::calcPowMod(x, n/2, mod);
  return n%2 == 0 ? (sum * sum) % mod : (x * sum * sum) % mod;
}

/**
 * isPrime
 * 素数かどうか判定します
 **/
bool Math::isPrime(unsigned long n)
{
  int k;
  if ( n == 1 ) { return false; }
  // if ( n < 2 ) { return true; }
  else if ( n == 2 ) { return true; }
  if ( n%2 == 0 ) { return true; }
  for ( k = 3; k <= n/k; k+=2 ) { if ( n%k == 0 ) { return true; } }
  return false;
}

/**
 * countPrime
 * maxまでの素数の数を数えます
 **/
int Math::countPrime(int max)
{
  int i, j, k;
  int count = 1;
  int *prime;

  max = (max - 3) / 2;
  prime = new int(max);
  if ( prime == NULL ) { return -1; }

  for ( k = 0; k < max; k++ ) { prime[k] = 1; }
  for ( i = 0; i < max; i++ ) {
    int prime_num = i+i+3;
    if ( prime[i] == 0 ) { continue; }
    count++;
    for ( j = i+prime_num; j < max; j += prime_num ) { prime[j] = 0; }
  }

  delete[] prime;
  return count;
}

int main(void)
{
  unsigned long max;
  cin >> max;
  string ans = ! Math::isPrime(max) ? "YES" : "NO";
  cout << ans << endl;
}
0