文章目录
- 质数
- 试除法判定质数
- 试除法分解质因数
- 朴素筛法求质数
- 埃氏筛法求质数
- 线性筛法求质数
- 约数
- 试除法求所有约数
- 试除法求所有约数之和
- 约数个数和约数之和
- 欧几里得算法
一、质数
1.试除法判定质数--O(sqrt(N))
原理：把从[2,n-1]中的每一个自然数作为除数来除n，如果n不能被其中的任意一个数整除，那么n就是素数。
优化：由于一个数的约数都是成对出现的。所以只需要枚举[2,sqrt(n)];
bool is_prime(int x)
{
if (x < 2) return false;
for (int i = 2; i <= x / i; i ++ )
if (x % i == 0)
return false;
return true;
}2.试除法分解质因数--O(logN)~O(sqrt(N))
原理：从[2,sqrt(n)]中枚举所有的质数，如果找到某一个素数i，则需要将n连续除以i得到m个i，然后将n中去除m个i的数，继续操作，如果最后一个数大于1，则得到最后一个质因子。
void divide(int x)
{
for (int i = 2; i <= x / i; i ++ )
if (x % i == 0)
{
int s = 0;
while (x % i == 0) x /= i, s ++ ;
cout << i << ' ' << s << endl;
}
if (x > 1) cout << x << ' ' << 1 << endl;
cout << endl;
}3.朴素筛法求质数--O(NlogN)
原理：对于n个数，从2开始枚举，依次将其倍数删去，如果枚举到该数仍存在则该数一定为质数，因为例如一个数p，枚举到它时还存在，说明它不是2~p-1中任何数的倍数，即该数为质数。
int primes[N],cnt;
bool st[N];
筛选出所有数的倍数
void get_primes(int n)
{
for (int i = 2; i <= n; i++)
{
if (st[i]) continue;
primes[cnt++] = i;
for (int j = i + i; j <= n; j += i) st[j] = true;//筛选出i的倍数
}
}4.埃氏筛法求质数--O(loglogN)
埃及筛法就是在朴素筛法的基础上，我们只用将质数的倍数删掉即可，因为一个合数可以写成几个质数的积，那么我们将所有质数的倍数删掉时，所有合数也被删掉了，这样可以将时间复杂度优化到O(nloglogn)，可粗略看作O(n)。
优化：通过只筛选质数的倍数即可。
int primes[N],cnt;
bool st[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;
}
}
}5.线性筛法求质数
对于某一个合数n，其只会被自己的最小质因子给筛掉。
int primes[N],cnt;
bool st[N];
void get_primes(int n) {
for(int i = 2; i <= n; i++) {
if(!st[i]) primes[ctn++] = i;
for(int j = 0; primes[j] <= n / i; j++) {
st[primes[j] * i] = true;
// 当下面的if条件成立时, primes[j]一定是i的最小质因子
if(i % primes[j] == 0) break;
}
}
}
二、约数
1.试除法求所有约数--O(sqrt(N))
原理：假设p是x的一个约数，那么x/p一定也是它的约数，所以只需枚举2 到 sqrt(n)的约数，并且可以直接通过运算获得sqrt(n) 之后对应的那个约数。
vector<int> get_divisors(int x)
{
vector<int> res;
for (int i = 1; i <= x / i; i ++ )
if (x % i == 0)
{
res.push_back(i);
if (i != x / i) res.push_back(x / i);
}
sort(res.begin(), res.end());
return res;
}2.试除法求所有约数之和
vector<int> get_divisors(int x)
{
vector<int> res;
for (int i = 1; i <= x / i; i ++ )
if (x % i == 0)
{
res.push_back(i);
if (i != x / i) res.push_back(x / i);
}
sort(res.begin(), res.end());
return res;
}3.约数个数和约数之和
unordered_map<int, int> primes;
//求约数个数
void get_divisors_numbers(int x)
{
for(int i=2;i<=x/i;i++)
while (x % i == 0)
{
x /= i;
primes[i]++;
}
if (x > 1) primes[x]++;
LL res = 1;
for (auto prime : primes) res = res * (prime.second + 1)%mod;
cout << res << endl;
}unordered_map<int, int> primes;
//求约数之和
void get_divisors_sumNumbers(int x)
{
for(int i=2;i<=x/i;i++)
while (x % i == 0)
{
x /= i;
primes[i]++;
}
if (x > 1) primes[x]++;
LL res = 1;
for (auto prime : primes) {
int p = prime.first, a = prime.second;
LL t = 1;
while (a--) t = (t * p + 1) % mod;
res = res * t % mod;
}
cout << res << endl;
}
4.欧几里得算法
原理：辗转相除法原理是设两数为a、b(a>b)，用gcd(a，b)表示a， b的最大公约数，r=a(mod b)为a除以b的余数，k为a除以b的商，即a÷b=k.....r。辗转相除法即是要证明gcd(a，b)=gcd(b， r)。辗转相除法，又名欧几里德算法。
int gcd(int a, int b)
{
return b ? gcd(b, a % b) : a;
}
