結果

問題 No.8030 ミラー・ラビン素数判定法のテスト
ユーザー yuppe19 😺
提出日時 2019-02-15 15:41:42
言語 C++14
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++14 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 2,333 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 591 ms
コンパイル使用メモリ 67,752 KB
最終ジャッジ日時 2026-05-12 03:52:45
合計ジャッジ時間 1,388 ms
ジャッジサーバーID
（参考情報） 		judge3_1 / judge1_0
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
main.cpp:4:13: error: 'uint64_t' does not name a type
    4 | using U64 = uint64_t;
      |             ^~~~~~~~
main.cpp:3:1: note: 'uint64_t' is defined in header '<cstdint>'; this is probably fixable by adding '#include <cstdint>'
    2 | #include <vector>
  +++ |+#include <cstdint>
    3 | using namespace std;
main.cpp:9:1: error: 'U64' does not name a type; did you mean 'S64'?
    9 | U64 ModMul(U64 a, U64 b, U64 modulus)
      | ^~~
      | S64
main.cpp:36:1: error: 'U64' does not name a type; did you mean 'S64'?
   36 | U64 ModPow(U64 value, U64 exponent, U64 modulus)
      | ^~~
      | S64
main.cpp: In function 'bool is_prime(S64)':
main.cpp:58:9: error: 'U64' was not declared in this scope; did you mean 'S64'?
   58 |     for(U64 p : {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}) {
      |         ^~~
      |         S64
main.cpp:58:61: error: expected primary-expression before ')' token
   58 |     for(U64 p : {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}) {
      |                                                             ^
main.cpp:58:61: error: expected ';' before ')' token
   58 |     for(U64 p : {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}) {
      |                                                             ^
      |                                                             ;
main.cpp:59:15: error: 'p' was not declared in this scope
   59 |       if(n == p)     { return true; }
      |               ^
main.cpp:60:14: error: 'p' was not declared in this scope
   60 |       if(n % p == 0) { return false; }
      |              ^
main.cpp:75:9: error: 'U64' was not declared in this scope; did you mean 'S64'?
   75 |         U64 enough;
      |         ^~~
      |         S64
main.cpp:77:17: error: 'enough' was not declared in this scope
   77 |                 enough = 1;
      |                 ^~~~~~
main.cpp:79:17: error: 'enough' was not declared in this scope
   79 |                 enough = 2;
      |                 ^~~~~~
main.cpp:81:17: err

ソースコード

diff #
raw source code 

#include <iostream>
#include <vector>
using namespace std;
using U64 = uint64_t;
using S64 = int64_t;

const S64 Primes[] = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37 };

U64 ModMul(U64 a, U64 b, U64 modulus)
{
  /*
	{
		S64 a2 = (S64)a;
		if (a2 >= 0)
		{
			S64 b2 = (S64)b;
			if (b2 >= 0)
			{
				if (!MulAsm(&a2, b2))
					return (U64)a2 % modulus;
			}
		}
	}
  */
	U64 result = 0;
	while (a != 0)
	{
		if ((a & 1) != 0)
			result = (result + b) % modulus;
		a >>= 1;
		b = (b << 1) % modulus;
	}
	return result;
}

U64 ModPow(U64 value, U64 exponent, U64 modulus)
{
	U64 w = 1;
	while (exponent > 0)
	{
		if ((exponent & 1) != 0)
			w = ModMul(w, value, modulus);
		value = ModMul(value, value, modulus);
		exponent >>= 1;
	}
	return w;
}


bool is_prime(S64 n)
{
	if (n <= 1)
		return false;
	if ((n & 1) == 0)
		return n == 2;
	if (n <= 1920000)
	{
    for(U64 p : {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}) {
      if(n == p)     { return true; }
      if(n % p == 0) { return false; }
    }
    /*
		if (n == 3)
			return true;
		if (n % 6 != 1 && n % 6 != 5)
			return false;
		S64 m = n / 6 * 2 + (n % 6 == 1 ? 0 : 1);
		size_t size;
		const U8* primes_bin = GetPrimesBin(&size);
		return (primes_bin[m / 8] & (1 << (m % 8))) != 0;
    */
	}

	// Miller-Rabin primality test.
	U64 enough;
	if (n < 2047)
		enough = 1;
	else if (n < 1373653)
		enough = 2;
	else if (n < 25326001)
		enough = 3;
	else if (n < 3215031751)
		enough = 4;
	else if (n < 2152302898747)
		enough = 5;
	else if (n < 3474749660383)
		enough = 6;
	else if (n < 341550071728321)
		enough = 7;
	else if (n < 3825123056546413051)
		enough = 9;
	else
	{
		// n < 2^64 < 318665857834031151167461
		enough = 12;
	}
	{
		U64 d = (U64)n - 1;
		U64 s = 0;
		while ((d & 1) == 0)
		{
			s++;
			d >>= 1;
		}
		for (U64 i = 0; i < enough; i++)
		{
			U64 x = ModPow(Primes[i], d, (U64)n);
			U64 j;
			if (x == 1 || x == (U64)n - 1)
				continue;
			bool probablyPrime = false;
			for (j = 0; j < s; j++)
			{
				x = ModPow(x, 2, (U64)n);
				if (x == (U64)n - 1)
				{
					probablyPrime = true;
					break;
				}
			}
			if (!probablyPrime)
				return false;
		}
		return true;
	}
}

int main(void) {
  int n; scanf("%d", &n);
  for(int loop=0; loop<n; ++loop) {
    S64 x; scanf("%ld", &x);
    printf("%ld %d\n", x, is_prime(x));
  }
  return 0;
}
0