数论--质数和约数

质数

质数:严格大于1,从2开始,只包含1和本身这两个约数,就是质数或者素数

质数的判定 (试除法)

1
2
3
4
5
6
7
8
9
10
11
12
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;
}


分解质因数 (试除法)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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;
}

朴素(埃氏)筛法求素数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int primes[N], cnt;     // primes[]存储所有素数
bool st[N]; // st[x]存储x是否被筛掉

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;
}
}

线性筛法求素数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int primes[N], cnt;     // primes[]存储所有素数
bool st[N]; // st[x]存储x是否被筛掉

void get_primes(int n)
{
for (int i = 2; i <= n; i ++ )
{
if (!st[i]) primes[cnt ++ ] = i;
for (int j = 0; primes[j] <= n / i; j ++ )
{
st[primes[j] * i] = true;//primes[j]一定是i的最小质因子
if (i % primes[j] == 0) break;
}
}
}

约数

试除法求约数

1
2
3
4
5
6
7
8
9
10
11
12
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;
}

约数个数和约数之和

1
2
3
如果 N = p1^c1 * p2^c2 * ... *pk^ck
约数个数: (c1 + 1) * (c2 + 1) * ... * (ck + 1)
约数之和: (p1^0 + p1^1 + ... + p1^c1) * ... * (pk^0 + pk^1 + ... + pk^ck)

求所有数乘积的约数个数

求所有数乘积的约数之和

欧几里得算法 (辗转相除法)

求最大公约数

1
2
3
4
5

int gcd(int a, int b)
{
return b ? gcd(b, a % b) : a;
}