【題解】Zerojudge a007 - 判斷質數

題目連結

題目大意

給定很多整數，問是不是質數。

題解

作法一

先找出 $\sqrt{2147483647}$ 以內的質數。對於每個數字 $n$，檢查是否有質數能整除即可。

找出給定範圍內所有的質數有許多作法。

1. 比較簡單的方法就是檢查每個數字是否有數字能整除他。假設我們要判斷 $k$ 是不是質數，拿 $2$ ~ $\sqrt{k}$ 去除 $k$ 看是否能夠整除。由於我們一共有 $\sqrt{2147483647}$ 個數字要檢查，每個數字又要從 $2$ 除到根號，因此這個作法預處理的時間複雜度為 $O(2147483647^{\frac{3}{4}})$。


2. 進階一點的作法可以用埃氏篩法 $O(n \log \log n)$ 或是線性篩 $O(n)$ 求出 $1$ ~ $n$ 以內所有的質數。

以下的程式碼是用線性篩找出質數。

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

vector<int> sieve(int N) {
	vector<bool> is_prime(N + 1, true);
	is_prime[0] = is_prime[1] = false;
	vector<int> primes;
	for(int i = 2; i <= N; i++) {
		if(is_prime[i]) {
			primes.push_back(i);
		}
		for(auto j : primes) {
			if(i * j > N) {
				break;
			}
			is_prime[i * j] = false;
			if(i % j == 0) {
				break;
			}
		}
	}
	return primes;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	auto primes = sieve(sqrt(INT_MAX) + 10);
	int n;
	while(cin >> n) {
		bool ok = true;
		for(auto p : primes) {
			if(n % p == 0) {
				if(n != p) {
					ok = false;
				}
				break;
			}
		}
		cout << (ok ? "質數" : "非質數") << "\n";
	}
	return 0;
}

作法二

Miller Rabin質數判定法，因為題目有保證輸入在 int 的範圍內，因此只需要檢測 $2, 7, 61$ 這三個數字。

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

int power(int a, int b, int m) {
	int res = 1;
	while(b) {
		if(b & 1) {
			res = 1LL * res * a % m;
		}
		a = 1LL * a * a % m;
		b >>= 1;
	}
	return res;
}

bool is_prime(int n) {
	if(n <= 4) {
		return n == 2 || n == 3;
	}
	int t = __builtin_ctz(n - 1);
	int m = (n - 1) >> t;
	for(auto x : {2, 7, 61}) {
		if(n == x) {
			return true;
		}
		int z = power(x, m, n);
		if(z == 1 || z == n - 1) {
			continue;
		}
		for(int i = 0; i < t; i++) {
			z = 1LL * z * z % n;
			if(z == 1) {
				return false;
			}
			if(z == n - 1) {
				break;
			}
		}
		if(z != n - 1) {
			return false;
		}
	}
	return true;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	while(cin >> n) {
		cout << (is_prime(n) ? "質數" : "非質數") << "\n";
	}
	return 0;
}

如果本文對您有幫助的話幫忙點擊廣告和分享吧！

© 若無特別註明，本站文章皆由 WeakMouse's Coding Blog 原創 ，轉載引用本文前請先留言告知。本文轉載請註明文章源自 WeakMouse's Coding Blog ，作者 ，並附上原文連結： 【題解】Zerojudge a007 - 判斷質數