一、素性判断
素数，又叫质数，是指一个整数，除了1和本身之外，还有其它的因数（注意：1不是素数）。因此，对于一个整数 \(n\)，我们只要检测 \([2, n - 1]\) 能否整除 \(n\)。
整除的定义：\(\exist\) \(a, b, k \in \mathbb{Z}\)，使得 \(a = kb\)，则称 \(b\) 整除 \(a\)，记 \(b\) \(|\) \(a\)。
若 \(d\) 是 \(n\) 的因数，则 \(\frac{n}{d}\) 也是 \(n\) 的因数。由 \(n = d \ast \frac{n}{d}\) 可知，\(min(d, \frac{n}{d}) \leq \sqrt{n}\)。同时，我们知道了一个因数，就能求出另一个因数。所以，我们只要检测 \([2, \sqrt{n}]\) 即可。
- 判断一个正整数的素性
// 检测n是否是素数
bool if_prime(int n)
{
// 遍历 [2, sqrt{n}]，素数要忽略1和本身
for (int i = 2; i * i <= n; i++)
{
if (n % i == 0)
return false;
}
return n != 1; // 1 不是素数
}
该算法的核心思想是判断因数。以下两个算法也用到了该思想：
- 枚举一个正整数的所有因数
// 枚举n的因数
vector<int> divisors(int n)
{
vector<int> ans;
// 因数要包含1和本身
for (int i = 1; i * i <= n; i++)
{
if (n % i == 0)
ans.push_back(i);
if (i != n / i) // i*i==n时，要忽略一个i
ans.push_back(n / i);
}
return ans;
}
- 分解一个正整数
// 将整数n分解成若干个素数，除1和本身
map<int, int> factors(int n)
{
map<int, int> ans; // 分解n后，有ans[i]个i
// n==1，特殊考虑
if (n == 1)
{
ans[n] = 1;
return ans;
}
// 1和本身总是因数，这里忽略
for (int i = 2; i * i <= n; i++)
{
// 可能有若干个i
while (n % i == 0)
{
ans[i]++; // 分解出一个i
n /= i;
}
}
if (n != 1) // n==1，已经分解完了
ans[n] = 1;
return ans;
}
二、埃氏筛法
2.1 问题描述
给定正整数 \(n\)，求出 \(n\) 以内有多少个素数。
2.2 问题简析
解决该问题需要用到埃氏筛法：先将 \([2, n]\) 内的整数写下来。接下来，开始筛数。每次筛数，保留最小的数 \(m\)，即素数，然后筛去 \(m\) 的倍数。经过多轮的筛数，留下的就都是素数了。
2.3 代码
#include <bits/stdc++.h>
using namespace std;
#define MAX 10000000
int n;
vector<int> ans;
bool is_prime[MAX];
int main()
{
scanf("%d", &n);
fill(begin(is_prime), end(is_prime), true);
for (int i = 2; i <= n; i++)
{
if (is_prime[i])
{
ans.push_back(i);
// 筛去 i 的倍数
for (int j = 2 * i; j <= n; j += i)
is_prime[j] = false;
}
}
printf("%d\n", ans.size());
return 0;
}
三、区间筛法
3.1 问题描述
给定正整数 \(a\) 和 \(b\)，求除 \([a, b)\) 内的素数个数。
3.2 问题简析
由上文可知，\(b\) 的最小质因数不大于 \(\sqrt{b}\)。所以，用 \([2, \sqrt{b})\) 就能筛去 \([a, b)\) 里的数。解释：
\[\begin{split} &\exist~m \in [2, \sqrt{b})，使得~m~|~b。假设~m~是素数，\\ &则遍历到~\sqrt{b}~之前，就能筛去~b。 \end{split} \]3.3 代码
#include <bits/stdc++.h>
using namespace std;
#define MAX 1000003
typedef long long ll;
ll a, b;
bool is_prime_mini[MAX]; // [2, sqrt(b))
bool is_prime[MAX]; // [a, b)
int main()
{
scanf("%lld%lld", &a, &b);
fill(begin(is_prime_mini), end(is_prime_mini), true);
fill(begin(is_prime), end(is_prime), true);
// 筛[2, sqrt(b))
for (int i = 2; (ll)i * i < b; i++)
{
if (is_prime_mini[i])
{ // 筛[2, sqrt(b))
for (int j = 2 * i; (ll)j * j < b; j += i)
is_prime_mini[j] = false;
// 筛[a, b)
ll j = a / i; // 向下取整，可能差一个i
if (j * i < a) j += 1; // 差一个i
for (j *= i; j < b; j += i)
is_prime[j - a] = false; // [a, b) 压缩到 [0, b - a)
}
}
int ans = 0;
for (ll i = a; i < b; i++)
if (is_prime[i - a])
ans++;
printf("%d\n", ans);
return 0;
}
该算法有几个注意点：
- 1、一般区间筛法中 \(a\) 和 \(b\) 都是较大的，所以要用
long long来存储。 - 2、区间一般默认左闭右开，所以两个循环判断条件都没有等号。
- 3、筛完 \([2, \sqrt{b})\) 后，再筛 \([a, b)\)，需要注意
j的取值。j应该为i的倍数，且j应该不小于 \(a\)，所以要先比较j与 \(a\) 的大小。
完
标签：prime,int,有关,算法,sqrt,因数,素数,ans From： https://www.cnblogs.com/hoyd/p/18013782