結果

問題 No.3030 ミラー・ラビン素数判定法のテスト
ユーザー unagiunagunagiunag
提出日時 2019-09-30 04:25:54
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
MLE  
実行時間 -
コード長 1,899 bytes
コンパイル時間 799 ms
コンパイル使用メモリ 75,212 KB
実行使用メモリ 934,876 KB
最終ジャッジ日時 2024-11-18 17:07:34
合計ジャッジ時間 72,888 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 MLE -
testcase_01 MLE -
testcase_02 MLE -
testcase_03 MLE -
testcase_04 TLE -
testcase_05 TLE -
testcase_06 TLE -
testcase_07 TLE -
testcase_08 TLE -
testcase_09 TLE -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <vector>
#include <iostream>
#include <cassert>

using namespace std;
using lint = long long;

class Prime {
private:
	vector<int> min_pf; // min_pf[i] = minimum prime factor of i
	vector<int> prime;

	// linear sieve https://cp-algorithms.com/algebra/prime-sieve-linear.html
	void sieve(int N) {
		min_pf[0] = min_pf[1] = -1;
		for (int i = 2; i < N; i++) {
			if (min_pf[i] == 0) {
				prime.push_back(i);
				min_pf[i] = i;
			}
			for (int j = 0; j < (int)(prime.size()); ++j) {
				if (prime[j] > min_pf[i] || i * prime[j] >= N) break;
				min_pf[i * prime[j]] = prime[j];
			}
		}
	}

public:
	Prime(int N = 110000000) : min_pf(N + 1) {
		assert(3 <= N);
		sieve(N + 1);
	}

	vector<pair<lint, int>> factorize(lint n) {
		vector<pair<lint, int>> res;
		for (lint i = 2; i * i <= n; i++) {
			if (n < (lint)min_pf.size()) break;
			int cnt = 0;
			while (n % i == 0) {
				cnt++;
				n /= i;
			}
			if (cnt) res.emplace_back(i, cnt);
		}

		if (n >= (lint)min_pf.size()) res.emplace_back(n, 1);
		else {
			int prev = min_pf[n], cnt = 0;
			while (n != 1) {
				int now = min_pf[n];
				n /= now;
				cnt++;
				if (prev != now) {
					res.emplace_back(prev, cnt);
					prev = now;
					cnt = 0;
				}
			}
		}
		return res;
	}

	// verified using boost miller_rabin_test https://wandbox.org/permlink/6YepW3J9SQNFwWxu
	bool isPrime(lint n) {
		if (n < (int)(min_pf.size())) return min_pf[n] == n;
		else if (n % 2 == 0 || n % 3 == 0) return false;
		else if (n % 6 != 1 && n % 6 != 5) return false;
		for (lint i = 5; i * i <= n; i += 6) {
			if (n % i == 0) return false;
			if (n % (i + 2) == 0) return false;
		}
		return true;
	}
};

int main(){
    
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	
	int N;
	cin >> N;
	
	vector<lint> x(N);
	for(int i = 0; i < N; i++) cin >> x[i];
	
	Prime p;
	for(int i = 0; i < N; i++) cout << x[i] << " " << p.isPrime(x[i]) << "\n";
    
}
0