质数
一、试除法判定质数
质数的定义:若一个正整数无法被除了1和它自身之外的任何自然数整除,则称该数为质数(或素数),否则称该正整数为合数。
整个自然数集合中,质数的数量不多,分布比较稀疏,对于一个足够大的整数N,不超过N的质数大约有\(\frac{N}{\ln N}\)个,即每\(\ln N\)个数中大约有一个质数。
试除法:
若一个正整数\(N\)为合数,则存在一个能整除\(N\)的数\(T\),其中\(2 \le T \le \sqrt{N}\)。
时间复杂度:\(O(\sqrt{N})\)
#include <iostream>
using namespace std;
bool is_prime(int n)
{
// 特判0和1这两个数,他们既不是质数,也不是合数
if (n < 2) return false;
// 从2开始依次试除,此处不使用i * i <= sqrt(n)是为了避免乘积溢出
for (int i = 2; i <= n / i; i ++ ) {
// 若该数能够被除了1和它自身之外的数整除,则其为合数
if (n % i == 0)
return false;
}
// 遍历结束后则证明该数只能被1和它自身整除,则其为质数
return true;
}
int main()
{
int n;
cin >> n;
while (n -- ) {
int a;
cin >> a;
if (is_prime(a)) puts("Yes");
else puts("No");
}
return 0;
}
二、分解质因数
算数基本定理:
任何一个大于 \(1\) 的正整数都能唯一分解为有限个质数的乘积,可写作:
其中 \(c_i\) 都是正整数,\(p_i\) 都是质数,且满足 $p_1 < p_2 < ... < p_m $。
结合质数判定的"试除法",扫描 \(2 \sim \sqrt{N}\) 的每个数 \(d\),如果 \(d\) 是质数,则除掉 \(N\) 里面所有的质因子 \(d\)。又由于 \(N\) 中最多只含有一个大于 \(\sqrt{N}\) 的因子,所以最后判断 \(N\) 是否大于 \(1\),若是则 \(N\) 即为质因子。
时间复杂度:\(O(\sqrt{N})\)
#include <iostream>
using namespace std;
void divide(int n)
{
for (int i = 2; i <= n / i; i ++ )
// 若i为质因数,则要将该因子除干净
if (n % i == 0) {
int s = 0; // s记录该质因子的次数
while (n % i == 0) {
n /= i;
s ++;
}
cout << i << ' ' << s << endl;
}
// 最多只有1个大于sqrt(n)的质因子
if (n > 1) cout << n << ' ' << 1 << endl;
puts("");
}
int main()
{
int n;
cin >> n;
while (n -- ) {
int a;
cin >> a;
divide(a);
}
return 0;
}
三、筛质数
给定一个整数 \(N\),求出 \(1 \sim N\) 之间的所有质数,称为质数的筛选问题。
3.1 朴素筛法
任意整数 \(x\) 的倍数 \(2x\), \(3x\), ...都不是质数,根据质数的定义,上述规则显然成立。则枚举 \(2 \sim n\) 的每个数,如果是质数,则将该范围内它的倍数都标记为合数。
时间复杂度:\(O(N\log N)\)
每一重循环分别会执行 \(\frac{n}{2}\),\(\frac{n}{3}\),...\(\frac{n}{n}\)次,则
\[\frac{n}{2} + \frac{n}{3} + ... + \frac{n}{n} = n(\frac{1}{2} + \frac{1}{3} + ... + \frac{1}{n}) \]又因为调和级数:
\[\sum_{k=1}^{n}\frac{1}{k} = \ln n + \gamma + \epsilon_k \]其中 \(c\) 为欧拉-马歇罗尼常数,约等于0.5772(无限不循环小数),\(\epsilon_k\) 约等于 \(\frac{1}{2k}\),并随着 \(k\) 趋于正无穷而趋于 \(0\)。又因为对数函数真值不变时,底数越大,函数值越小,图像越靠近x轴,所以:
\[O(\ln N) = O(\log_e N) < O(\log_2N) = O(\log N) \]所以我们可以将时间复杂度记作\(O(N\log N)\)
void get_primes(int n)
{
for (int i = 2; i <= n; i ++ ) {
// 判断是否为质数,若是质数则存起来
if (!st[i]) primes[cnt ++] = i;
// 不管i是质数还是合数,都将其倍数标记为合数
for (int j = i; j <= n; j += i) st[j] = true;
}
}
3.2 埃氏筛法(Eratosthenes 筛法)
分析朴素筛法的过程易知,在遍历2和3时,都会把6标记为合数,因此可以对其进行优化,利用所有的质数就可以标记筛除所有的合数。而对于一个足够大的整数N,不超过N的质数大约有\(\frac{N}{\ln N}\)个,则大致估计时间复杂度由朴素筛法的 \(O(N\ln N)\) 变为 \(O(N\ln N / \ln N) = O(N)\),接近线性。
实际的时间复杂度:\(O(N\log \log N)\)
void get_primes(int n)
{
for (int i = 2; i <= n; i ++ )
if (!st[i]) {
primes[cnt ++] = i;
// 利用质数筛除值为其倍数的合数
for (int j = i + i; j <= n; j += i) st[j] = true;
}
}
3.3 欧拉筛法(线性筛法)
优化后的埃氏筛法依然会重复标记合数,例如:\(12\) 既会被 \(2\) 又会被 \(3\) 标记,\(12=6*2\),\(12=4*3\)。线性筛法通过“从大到小累积质因子”的方式标记每一个合数,即让 \(12\) 仅有 \(3*2*2\) 这一种产生方式。使得每个合数只会被他的最小质因子筛一次,时间复杂度为 \(O(N)\)。
void get_primes(int n)
{
// 依次考虑2~N的每一个数i
for (int i = 2; i <= n; i ++ ) {
// 若为质数,则存起来
if (!st[i]) primes[cnt ++] = i;
// 扫描不大于 n/i 的每个质数(因为primes[j]*i>n时 筛除大于n的合数没有意义)
for (int j = 0; primes[j] <= n / i; j ++ ) {
// 利用最小质因子筛除合数
st[primes[j] * i] = true;
/*
* 如果 i % primes[j] != 0
* 代表 i 的最小质因子还没有找到,即 i 的最小质因子应该大于 primes[j]
* 则 primes[j] 就应该是 primes[j] * i 的最小质因子
* 所以 primes[j] * i 被 primes[j] 筛除
*
* 如果 i % primes[j] == 0
* 代表 i 的最小质因子就是 primes[j]
* 则后续的 primes[j+k] * i 应该被 primes[j] 筛除
* 所以跳出循环,在之后的循环轮次(i更大时)筛除
*/
if (i % primes[j] == 0) break;
}
}
}
标签:frac,筛法,ln,33,质数,int,算法,合数
From: https://www.cnblogs.com/I-am-Sino/p/16970788.html