素数
素数和合数
定义
若 \(p \in \Zeta\)，且 \(p \not= 0, \pm1\)，其约数集合中的元素只有 \(1\) 和 \(p\) 本身，那么称 \(p\) 为素数。
若 \(a \in \Zeta\)，且 \(a \not= 0, \pm1\)， \(a\) 不为素数，则为合数。
素数一般指正的素数。
素数计数
\(\pi(x)\) 表示小于或等于 \(x\) 的素数个数。随 \(x\) 增大，近似结果：
\(\pi(x) \sim \frac{x}{\ln(x)}\)。
素数判定
试除。枚举 \(1 \sim \sqrt{n}\) 整数，看是否能够整除。
bool isPrime(a) {
if (a < 2) return 0;
for (int i = 2; i * i <= a; ++i)
if (a % i == 0) return 0;
return 1;
}
素数筛法
-
埃氏筛。
对于任意大于 \(1\) 的正整数 \(n\) ，那么它的 \(x\) 倍为合数\((x > 1)\)。
如果我们从小到大考虑每个数，然后同时把当前这个数的所有（比自己大的）倍数记为合数，那么运行结束的时候没有被标记的数就是素数了。
vector<int> prime;
bool is_prime[N];
void Eratosthenes(int n) {
is_prime[0] = is_prime[1] = false;
for (int i = 2; i <= n; ++i)
is_prime[i] = true;
int x = sqrt(n);
for (int i = 2; i <= x; ++i) {
if (is_prime[i])
for (int j = i * i; j <= n; j += i)
is_prime[j] = false;
}
for (int i = 2; i <= n; ++i)
if (is_prime[i])
prime.push_back(i);
}
时间复杂度为 \(\Omicron(n \log \log n)\)。
线性筛
可以注意到， 埃氏筛法仍有优化空间，它会将一个合数重复多次标记。
让每个合数都只被标记一次即可。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e8+10;
const int maxm = 1e7;
int v[maxn],prime[maxm]; // v[i] 表示 i 的最小质因子
int n, q, cnt=0;
void is_prime() { // 线性筛
memset(v, 0, sizeof(v));
for(int i=2; i<=n; ++i) {
if( !v[i] ) {
v[i] = i;
prime[++cnt] = i;
}
for(int j=1; j<=cnt; ++j) {
if(prime[j] > v[i] || prime[j] > n/i)
break;
v[i*prime[j]] = prime[j];
}
}
}
int main() {
scanf("%d%d", &n, &q);
is_prime();
while(q--) {
int x;
scanf("%d", &x);
printf("%d\n", prime[x]);
}
return 0;
}
区间筛法
using ll = long long;
bool isprime[maxn], primepart[maxn];
void func(ll l, ll r) {
for (ll i = 0; i * i <= r; ++i)
primepart[i] = 1;
primepart[1] = 0;
for (int i = 0; i <= r - l; ++i)
isprime[i] = 1;
for (ll i = 2; i * i <= r; ++i) {
if (primepart[i]) {
for (ll j = i * i; j * j <= r; j += i)
primepart[j] = 0;
for (ll j = max(2ll, (l + i - 1) / i) * i; j <= r; j += i)
isprime[j - l] = 0;
}
}
int ans = 0;
for (ll i = l; i <= r; ++i)
if (isprime[i - l] && i != 1)
ans++;
printf("%d\n", ans);
return;
}
相关题目
质因子分解
由唯一分解定理得。
void divide(int n) {
m = 0;
int t = sqrt(n);
for(int i=2; i<=t; ++i) {
if(n % i == 0) { // 此处能整除n的i一定是质数
p[++m] = i; c[m] = 0;
while(n % i == 0) {
n /= i; c[m]++;
}
}
}
if(n > 1) { // 原始的n是质数或者原始的n中最大的质因子大于 sqrt(n)
p[++m] = n; c[m] = 1;
}
}
约数
定义
若 $n \in $ \(\Zeta\)，$d \in $ $ \Zeta $， \(n\) \(\%\) \(d\) \(=\) \(0\)，则称 \(d\) 是 \(n\) 的约数，\(n\) 是 \(d\) 的倍数，记作 $ d \mid n $。
算数基本定理
引理
设 \(p\) 是素数，\(p | a_1a_2\)，那么 \(p | a_1\) 和 \(p|a_2\) 至少有一个成立。
唯一分解定理
设有 \(a \in \Nu^*\)，那么其一定可以表示为若干个素数的乘积。
标准素因数分解式
设有 \(a \in \Nu^*\)，必有：
\(a=p_1^{c_1}p_2^{c_2}...p_m^{c_m}, p_1 < p_2 <...< p_m\)
称为正整数 \(a\) 的标准素因数分解式。
算数基本定理与算数基本引理，两个定理等价。
算数基本定理的推论
在算数基本定理中，若 \(n \in \Nu^*\) 被唯一分解为 \(n = p_1^{c_1}p_2^{c_2}...p_m^{c_m}\)，其中 \(c_i \in \Nu^*\)，\(p_i\) 都是质数，且满足 \(p_1 < p_2 < ...<p_m\)，则 \(n\) 的正约数集合可写作：
{\(p_1^{b_1}p_2^{b_2}...p_m^{b_m}\)} ，\(0 \leq b_i \leq c_i\)
\(n\) 的正约数个数为：
\(\prod\limits^{m}_{i=1}\big( \sum\limits^{c_i}_{j=0}(p_i)^j \big)\)
求\(N\) 的正约数集合——试除法
若 \(d \geq \sqrt{N}\) 是 \(N\) 的约数，则 $ d \mid N$ 也是 \(N\) 的约数。也就是说，除完全平方数外，约数总是成对出现的。
据此可得：
gugu.
时间复杂度为 \(\Omicron(\sqrt{N})\)。
试除法的推论
对于一个 \(n \in \Zeta\)，其约数个数的上界为 \(2 \sqrt{n}\)。
求 \(1 \sim N\) 每个数的正约数集合——倍数法
gugu.
时间复杂度为 \(\Omicron(N +N/2+N/3+...+N/N)=\Omicron(N\log{N})\)。
倍数法的推论
\(1 \sim N\) 每个数的约数个数总和大约为 \(N\log{N}\)。
例题
最大公约数
定义
若自然数 \(d\) 同时是自然数 \(a\) 和 \(b\) 的约数，则称 \(d\) 是 \(a\) 和 \(b\) 的公约数。
在所有 \(a\) 和 \(b\) 的公约数中最大的一个数称为 \(a\) 和 \(b\) 的最大公约数。记作 \(\gcd(a, b)\)。
若自然数 \(d\) 同时是自然数 \(a\) 和 \(b\) 的倍数，则称 \(d\) 是 \(a\) 和 \(b\) 的公倍数。
在所有 \(a\) 和 \(b\) 的公倍数中最大的一个数称为 \(a\) 和 \(b\) 的最大公倍数。记作 \(\text{lcm}(a, b)\)。
同理即可定义多个数的最大公约数与最大公倍数。
定理
\(\forall a,b \in \Nu, \gcd(a,b)*\text{lcm}(a,b)=a*b\)。
求 \(\gcd\) 代码实现
int gcd(int a, int b) {
return b ? gcd(b, a%b) : a;
}
例题
数论分块
引入
\(f(n)=\sum\limits^{n}_{i=1} \lfloor \frac{n}{i} \rfloor\)，给定一个 \(n\) ，求 \(f(n)\) 的值。
需要整除分块的知识。
在给定一个 \(n\) 的前提下，可以发现 \(\lfloor \frac{n}{i} \rfloor\) 的取值在连续一段区间内相同，故可以分为若干块分别进行计算。这就是整除分块的核心思想。
分块数量（时间复杂度分析）
给定一个 \(n\) ，设有集合 \(A = \{x | x = \lfloor \frac{n}{i} \rfloor,1 \leq i \leq n,i \in \Zeta \}\)，\(card(A) \leq 2\sqrt{n}\)。
标签：prime,约数,数论,合数,基础,sqrt,int,素数 From： https://www.cnblogs.com/foreverlcrun0817/p/18262381