数学知识

算数基本定理

任何大于 1 的整数是质数或独一无二的质数乘积（不理次序）。

任何一个大于1的自然数n都可以表示为素数的乘积形式：

。其中，是素数，是大于等于1的整数，并且这种分解方式是唯一的。

质数

在大于1的整数中，如果只包含1和本身这两个约数，就被称为质数，或者叫素数。

  1. 质数的判定——试除法 O(sqrt(n))

    由于约数是成对出现的，所以n的最大约数只能是​

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
#include <iostream>
#include <algorithm>

const int N = 110;
int a[N];

using namespace std;

bool is_prime (int n)
{
    if (n < 2)  return false;
    for  (int i = 2; i <= n/i; i ++)
         {
        	if (n % i == 0)
           		 return false;
         }
    return true;
}


int main()
{
    int n;
    cin >> n;
    for (int i = 0; i < n ; i++)    cin >> a[i]; 

     for (int i = 0; i < n ; i++)    
        {
        if(is_prime (a[i]))
            cout << "Yes" << endl;
        else
            cout << "No" << endl;
        }
        
        return 0;

}

  1. 分解质因数 O(sqrt(n))

    • 质因数的底数指的是质数的基数，比如在分解12=2×2×3的式子中，2和3就是底数。 而指数指的是底数出现的次数,底数2的指数为2，底数3的指数为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
36
37
38
39
40
41
42
43
44
#include <iostream>
#include <algorithm>

const int N = 110;
int a[N];


using namespace std;

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;
        puts ("");
}




int main()
{
    int n;
    cin >> n;
    for (int i = 0; i < n ; i++)    cin >> a[i]; 

     for (int i = 0; i < n ; i++)    
        {
        divide (a[i]);  
        }
        
        return 0;

}