【題解】Zerojudge a121 - 質數又來囉

題目連結

題目大意

給定 $a$ 和 $b$，求 $a \sim b$ 中有多少個質數。

題解

判斷質數的幾種方法我有在【題解】Zerojudge a007 - 判斷質數這篇介紹，直接搬過來這題就能 AC 了。以下的 code 使用的是文章中所提到的 Miller Rabin 質數判定法。

#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 a, b;
	while(cin >> a >> b) {
		int ans = 0;
		for(int i = a; i <= b; i++) {
			if(is_prime(i)) {
				ans++;
			}
		}
		cout << ans << "\n";
	}
	return 0;
}

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

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