【基础数学】质数，约数，分解质因数，GCD，LCM

1.质数：

　　质数（prime number）又称素数，有无限个。一个大于1的自然数，除了1和它本身外，不能整除以其他自然数（质数），换句话说就是该数除了1和它本身以外不再有其他的因数。

2.约数：

　　如果一个整数能被两个整数整除，那么这个数就是着两个数的约数。约数是有限的，一般用最大公约数。例如 24的约数是1，2，3，4，6，8，12，24

3.计算约数和：

　　在数论中有种,把一个数分解成N个素数的积,再把这些素数的指数加一后,全部相乘的积就是约数的个数了。

　　例如:36 = 2^2 * 3^2 指数加一的积就是:(2+1)*(2+1) = 9;36有9个约数吧。
　　24 = 2^3 * 3 指数加一的积就是:（3+1)*(1+1) = 8;24就有8个约数。

 1 int check(int n){
 2     int i,sum = 1;
 3     memset(arry,0,sizeof(arry));
 4     for(i = 2;i <=n;i++){
 5         while(n!=i){
 6             if(n%i == 0){
 7                 arry[i]++;
 8                 n/=i;
 9             }            
10             else
11                 break;
12         }
13     }
14     arry[n]++;
15     for(int j = 1;j <= 9;j++){
16         if(arry[j]){
17             arry[j]+=1;
18             sum*=arry[j];
19         }
20     }
21     return sum;
22 }

3.分解质因数：

1 void check(int n){
2     int n1 = n,sum = 0;
3     for(int j = 2;j<=sqrt(n);j++){
4         while(n1 % j == 0){
5             n1 /= j;
6             cout << j << "	";
7         }
8     }cout << n1;
9 }

4.GCD（最大公约数）

　　　　两个数：

 1     scanf("%d%d",&a,&b);
 2         int a1 = a,b1 = b;
 3         if(a < b){
 4             temp = a;
 5             a = b;
 6             b = temp;
 7         }
 8         while(b != 0){
 9             temp = a % b;
10             a = b;
11             b = temp;
12         }
13         printf("%d",a);

　　　　多个数：　

 1 for(i = 0;i<n;i++){
 2         scanf("%d",&arry[i]);
 3     }
 4     //获得最小值
 5     min = arry[0];
 6     for(int j = 1;j<3;j++){
 7         if(arry[j] < min)
 8             min = arry[j];
 9     }
10     for(a = min;a>0;a--){
11         int sum = 0;
12         for(i = 0;i<n;i++){
13             sum+=arry[i]%a;
14         }
15         if(sum == 0)
16             break;
17     }
18     printf("%d
",a);

5.LCM（最小公倍数）

　　　　两个数：先计算出A,B的最大公约数C，LCM = A*B/C

　　　　多个数：先求最大公约数，各个数除这个最大公约数所得的各个数，相乘，再乘以这个最大公约数可得这几个数的最小公倍数