質數與因數
質數
質數為因數只有 和自己的數，質數問題在程式競賽中常常遇到，通會建立質數表來查詢質數。
一般篩法
每找到一個質數 ，就知道 都不是質數，把他們從候選名單剃除。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 | vector<int> p;
bitset<MAXN> is_notp;
void PrimeTable(int n)
{
is_notp.reset();
is_notp[0] = is_notp[1] = 1;
for (int i = 2; i <= n; i++)
{
if (is_notp[i])
continue;
p.push_back(i);
for (int j = i * i; j <= n; j += i)
{
is_notp[j] = 1;
}
}
}
|
複雜度可到 ，如果不從平方開始剃除，則會退化至
線性篩法
每個合數都只被其最小質因數剔除，此算法時間複雜度為 。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 | vector<int> p;
bitset<MAXN> is_notp;
void PrimeTable(int n)
{
is_notp.reset();
is_notp[0] = is_notp[1] = 1;
for (int i = 2; i <= n; ++i)
{
if (!is_notp[i])
p.push_back(i);
for (int j = 0; j < (int)p.size(); ++j)
{
if (i * p[j] > n)
break;
is_notp[i * p[j]] = 1;
if (i % p[j] == 0)
break;
}
}
}
|
程式碼關鍵在於 if (i % p[j] == 0) ，由於 裡面的元素都是遞增的，當這行成立，代表 的 最小質數， 都是 的倍數，都已經被 剔除（例如： 的最小質因數為 ， 都是 的倍數，他們會被 剔除），因此不必再篩下去。
因數
我們能將任意一個正整數做質因數分解，形式為 ，根據此形式，我們可以求出任一正整數的因數個數及因數總和
最大公因數
最大公因數 (Greatest Common Divisor, GCD)，可以用輾轉相除法求得。
| int GCD(int a, int b)
{
if (b == 0)
return a;
return GCD(b, a % b);
}
|
複雜度為 ，最慘狀況發生在兩數為費式數列相鄰項時， C++<algorithm> 有內建的 __gcd 可以用。
最小公倍數 (Least Common Multiple,LCM)，則為兩數相乘再除以他們的 GCD，為避免溢位狀況，可先將一數除以 GCD，再乘以另外一數。
質因數分解
質因數分解
給定一個數字 ，請列出他的所有質數。
質因數是一道常見的題目，以下有幾個要點：
- 只要枚舉所有 的質數。
-
在質因數分解的過程中會一直被更新，當找到 的一個質數 ，請將 除以 得到新的 ，縮小搜尋範圍，若是新的 還可被 整除，重複上述動作，直到 無法被 整除。
- 最後再檢查 是否為 ，若不是，則 也是質數。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 | void primeFactorization(int n)
{
for (int i = 0; i < (int)p.size(); ++i)
{
if (p[i] * p[i] > n)
break;
if (n % p[i])
continue;
cout << p[i] << ' ';
while (n % p[i] == 0)
{
n /= p[i];
}
}
if (n != 1)
{
cout << n << ' ';
}
cout << '\n';
}
|
歌德巴赫猜想
- 強歌德巴赫猜想：任何 的偶數都可以寫成兩個質數的和。
- 弱歌德巴赫猜想：任何 的奇數都可以寫成三個質數的和。
UVa 00543 - Goldbach's Conjecture
把偶數 寫成兩個質數的和。
歌德巴赫猜想基本練習，建立質數表，從頭開始枚舉奇數 ，判斷 和 是否皆為質數。
參考程式碼
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26 | #include <iostream>
#include <cstdio>
using namespace std;
#define N 20000000
int ox[N], p[N], pr;
void PrimeTable(){
ox[0] = ox[1] = 1;
pr = 0;
for (int i = 2; i < N; i++){
if (!ox[i]) p[pr++] = i;
for (int j = 0;i*p[j]<N&&j < pr; j++)
ox[i*p[j]] = 1;
}
}
int main(){
PrimeTable();
int n;
while (cin>>n,n){
int x;
for (x = 1;; x += 2)
if (!ox[x] && !ox[n - x])break;
printf("%d = %d + %d\n", n, x, n - x);
}
}
|
CodeForces 735D - Taxes
給定整數 ，求 最少可以拆成多少個質數的和。
- 如果 是質數，則答案為 。
- 如果 是偶數(不包含 )，則答案為 (強歌德巴赫猜想)。
- 如果 是奇數且 是質數，則答案為 (2 + 質數)。
- 其他狀況答案為 (弱歌德巴赫猜想)。
參考程式碼
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34 | #pragma GCC optimize("O2")
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, L, R) for (int i = L; i < (int)R; ++i)
#define FORD(i, L, R) for (int i = L; i > (int)R; --i)
#define IOS \
cin.tie(nullptr); \
cout.tie(nullptr); \
ios_base::sync_with_stdio(false);
bool isPrime(int n)
{
FOR(i, 2, n)
{
if (i * i > n)
return true;
if (n % i == 0)
return false;
}
return true;
}
int main()
{
IOS;
int n;
cin >> n;
if (isPrime(n))
cout << "1\n";
else if (n % 2 == 0 || isPrime(n - 2))
cout << "2\n";
else
cout << "3\n";
}
|
例題練習