题解 | 判断质数
判断质数
https://www.nowcoder.com/practice/9f418ff48b5e4e879f398352bed6118d
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 1e6 + 5;
bool isPrime(ll n)
{
if (n <= 3)
return n > 1;
if (n % 2 == 0 || n % 3 == 0)
return false;
for (ll i = 5; i * i <= n; i += 6)
{
if (n % i == 0 || n % (i + 2) == 0)
return false;
}
return true;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
ll n;
cin >> n;
if (isPrime(n))
cout << "Yes" << '\n';
else
cout << "No" << '\n';
return 0;
}
本题考查质数的判断，使用6*k+1优化完成对离散大数的判断，算法较为简洁。
查看5道真题和解析
