結果

問題 No.36 素数が嫌い！
ユーザー MaxMellon
提出日時 2015-10-05 22:52:40
言語 C++11（廃止可能性あり）
(gcc 13.3.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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 4
other AC * 10 WA * 16
権限があれば一括ダウンロードができます

ソースコード

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