算法基础-数学知识-质数、约数

质数

埃及筛虽然用的不多，大多使用线性筛，但是埃及筛的思想很重要

试除法判定质数

AcWing 866. 试除法判定质数

bool isPrime(int x)
{
   if (x < 2) return false;
    for (int i = 2; i <= x / i; i ++ )//不要用开方函数或者i*i小于x。开方函数慢，i*i可能越界
        if (x % i == 0)
            return false;
    return true;
}
1
2
3
4
5
6
7
8

AcWing 867. 分解质因数

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

void get_prime_factor(int x)
{
    for (int i = 2; i <= x / i; ++ i)
    {
        if (x % i == 0) 
        {
            cout << i << " ";
            int t = 0;
            while (x % i == 0) x /= i, t ++;
            cout << t << endl;
        }
    }

    if (x > 1) cout << x << " 1" << endl;
    cout << endl;
    return ;
}
void solve()
{
    int n;
    cin >> n;
    while (n --)
    {
        int x;
        cin >> x;
        get_prime_factor(x);
    }
}
int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T = 1;
    //cin >> T;
    while (T --) solve();
    return 0;
}
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
44
45
46
47
48

晒质数

埃及筛

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
const int N = 1e6 + 10;//不太记得最多多少个质数了
int primes[N];
bool st[N];
int get_prime(int x)
{
    int cnt = 0;
    for (int i = 2; i <= x; ++ i)
    {
        if (st[i]) continue;
        primes[cnt ++ ] = i;
        for (int j = i + i; j <= x; j += i)//将每个数的倍数筛掉，有倍数的一定是合数
            st[j] = true;
    }
    return cnt;
}
void solve()
{
    int x;
    cin >> x;
    cout << get_prime(x);           
}
int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T = 1;
    //cin >> T;
    while (T --) solve();
    return 0;
}
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

线性筛

在埃及筛上优化了一下，每个数字只会被筛掉一次，因此是线性的

int get_prime(int x)
{
    int cnt = 0;
    for (int i = 2; i <= x; ++ i)//第一个循环和埃及筛的意义不一样
    {
        if (!st[i]) primes[cnt ++ ] = i;
        for (int j = 0; primes[j] <= x / i; ++ j)//不用j < cnt，因为primes[j] <= x / i的时候j一定 >= cnt
        {
            //prime[j] * i 只会会在pj * i / pj的时候被筛掉
            //因为我们保证了pj是其最小质因子
            st[primes[j] * i] = true;//每个合数分解到最后都是由一个个质数组成的
            if (i % primes[j] == 0) break;//线性筛算法精髓所在，保证primes[j]始终是每个被筛掉的数的最小质因子
            /*当 i 能够被 primes[j] 整除时，即 i % primes[j] == 0，说明 i 这个数已经被标记为合数，并且 primes[j] 是它的最小质因子。		   此时，对于任意能被 i 整除的数 k，一定存在一个质因子 p，使得 p 大于等于 primes[j]。
            因为如果存在一个质因子 p，使得 p 小于 primes[j]，那么它一定在之前的循环中就被标记为合数了，矛盾。
由于在之前的循环中，所有大于 primes[j] 的质数都已经被筛选出来，因此，对于任意能被 i 整除的数 k，它的最小质因子一定大于等于 primes[j]。因此，当在后续的迭代中枚举 primes[j] * k 的倍数时，这些数的最小质因子一定大于等于 primes[j]，并且会被其它的质数标记为合数。

例如，当 i 为 6，primes[j] 为 2 时，6 已经被标记为合数，而后续能被 6 整除的数，如 12（2 * 6）、18（3 * 6）等，它们的最小质因子一定是 2 或 3，而不会是小于 2 的素数。因为小于 2 的素数已经在之前的循环中被筛选出来了
   */
        }                          
    }
    return cnt;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

约数

试除法求约数

试除法就是枚举

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
const int N = 1e5 + 10;
int divsors[N];
int cnt;
int get_divsors(int x)
{
    memset(divsors, 0, sizeof divsors);
    cnt = 0;
    for (int i = 1; i <= x / i; ++ i)
    {
       if (x % i == 0) 
       {
           divsors[cnt ++ ] = i;
           if (i != x / i) divsors[cnt ++] = x / i;
       }
    }
    sort(divsors, divsors + cnt);
}
void solve()
{
    int n;
    cin >> n;
    while (n -- )
    {
        int x;
        cin >> x;
        get_divsors(x);
        for (int i = 0; i < cnt; ++ i)
        {
            cout << divsors[i] << " ";
        }
        cout << endl;
    }
}
int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T = 1;
    //cin >> T;
    while (T --) solve();
    return 0;
}
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
44
45
46
47
48
49
50
51
52

约数个数与约数之和

AcWing 870. 约数个数

重点是以下
约数的意义

计算个数的时候为什么要加1

 #include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long LL;
const int N = 1e5 + 10, p = 1e9 + 7;
unordered_map<int, int> divsorts;
void get_divsors(int x)
{
    for (int i = 2; i <= x / i; ++ i)
    {
        while (x % i == 0)
        {
            divsorts[i] ++;
            x /= i;
        }
    }
    if (x > 1) divsorts[x] ++;
}
void solve()
{
    int n;
    cin >> n;
    while (n --)
    {
        int x;
        cin >> x;
        get_divsors(x);
    }
    int res = 1;
    for (auto cnt : divsorts) res = (LL)res * (cnt.second + 1) % p;
    cout << res;
}
int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T = 1;
    //cin >> T;
    while (T --) solve();
    return 0;
}
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
44
45
46
47
48
49

AcWing 871. 约数之和

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long LL;
const int N = 1e5 + 10, mod = 1e9 + 7;
unordered_map<int, int> divsorts;
void get_divsors(int x)
{
    for (int i = 2; i <= x / i; ++ i)
    {
        while (x % i == 0)
        {
            divsorts[i] ++;
            x /= i;
        }
    }
    if (x > 1) divsorts[x] ++ ;
}
void solve()
{
    int n;
    cin >> n;
    while (n --)
    {
        int x;
        cin >> x;
        get_divsors(x);
    }
    LL res = 1;
    for (auto divsort : divsorts) 
    {
        LL t = 1;
        int a = divsort.first, b = divsort.second;
        while (b -- ) t = (t * a + 1) % mod;
        res = res * t  % mod;
    }
    cout << res;
}
int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T = 1;
    //cin >> T;
    while (T --) solve();
    return 0;
}
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
44
45
46
47
48
49
50
51
52
53
54
55

欧几里德求最大公因数

求最大公因数还有一个算法就是根相减损术
A：a，B：b，D：a - m*b（a % b）

递归到最后就是 x和0的最大公约数就是x

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

int get_max_divsort(int a, int b)
{
    if (b != 0) return get_max_divsort(b, a % b);
    else return a;
}
void solve()
{
    int n;
    cin >> n;
    while (n --)
    {
        int a, b;
        cin >> a >> b;
        int res = get_max_divsort(a, b);
        cout << res << endl;
    }
}
int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T = 1;
    //cin >> T;
    while (T --) solve();
    return 0;
}
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