基本原理
素数，又叫质数，除了1和它本身以外不再有其他的因数。
代码模板
1
2
3
4
5
6
7
8
9
10
| 1） 时间复杂度是O(n)
---------------------
bool prime(int x){
if(x <= 1) return false;
for(int i = 2; i < x; 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
| 2）时间复杂度O( √n)
----------------------
bool prime(int x){
if(x <= 1) return false;
for(int i = 2; i <= sqrt(x + 0.5); 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
|
3）时间复杂度O( √n)
----------------------
bool prime(int x){
if(x <= 1) return false;
for(int i = 2; i * i <= x; 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 Eratosthenes(){
int m=sqrt(maxn+0.5);
for(int i=2;i<=m;i++){
if(!vis\[i\])
for(int j=i*i;j<=maxn;j+=i)
vis\[j\]=1;
}
}
|
简单应用
预处理每个数的所有质因数
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
35
| #include<cstdio>
#include<vector>
using namespace std;
const int N = 100000 + 5;
vector<int > prime_factor\[N\];
void init(){
for(int i = 2; i < N; i ++){
if(prime_factor\[i\].size() == 0){
for(int j = i; j < N; j += i){
prime\_factor\[j\].push\_back(i);
}
}
}
}
int main(){
init();
}
* * *
|
预处理每个数的所有因数
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
| #include<cstdio>
#include<vector>
using namespace std;
const int N = 100000 + 5;
vector<int > factor\[N\];
void init(){
for(int i = 2; i < N; i ++){
for(int j = i; j < N; j += i){
factor\[j\].push_back(i);
}
}
}
int main(){
init();
}
* * *
|
预处理每个数的质因数分解
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
35
36
37
38
39
40
41
42
43
| #include<cstdio>
#include<vector>
using namespace std;
const int N = 100000 + 5;
vector<int > prime_factor\[N\];
void init(){
int temp;
for(int i = 2; i < N; i ++){
if(prime_factor\[i\].size() == 0){
for(int j = i; j < N; j += i){
temp = j;
while(temp % i == 0){
prime\_factor\[j\].push\_back(i);
temp /= i;
}
}
}
}
}
int main(){
init();
}
|
