Algorithm9.2 数论入门
[TOC]
数论基础
最大公约数gcd
int gcd(int a,int b) { return (b>0)?gcd(b, a%b):a; }
利用的就是欧几里得原理
int gcd(int a, int b) { return (b<=0)?a:gcd(b, a%b); }
最大公约数[gcd]与最小公倍数[gld]乘积 == 这两个数的乘积
a*b = gcd(a, b)*gld()
最小公倍数[gld]
可以利用最大公约数倒推回去，也就是gld(a, b)=a*b/gcd(a, b)
质数
判断1～n中的所有质数
1、基础：O(n^2)复杂度，遍历，遍历的边界从3～sqrt(x)
bool isprime(int x){
for (int i = 3; i <= sqrt(x); ++i) if (x%i == 0) return false;
return true;
}
2、埃拉托斯特尼筛：O(nlogn)复杂度
3、线性筛：O(n)
prime是质数列表，isprime
#define maxn 10000010
int vis[maxn], prime[maxn], isprime[maxn];
void Prime()
{
for(int i=2; i<=b; i++)
{
if(!vis[i]) prime[cnt++] = i, isprime[i] = 1;
for(int j=0; j<cnt&&i*prime[j]<=b; j++)
{
vis[i*prime[j]] = i;
if(i%prime[j]==0) break;
}
}
}
b = 100; // 设置筛的边界
LPrime();
for (int i = 5; i < 20; ++i) {
printf("%d %d %d\n", i, prime[i], isprime[i]); // prime是按照顺序的素数存放进来， isprime是索引的数是否为质数
}