1.核心思想

1. 质数判断：试除法
2. 分解质因数：任何一个数 n ，一定能够表示成 n = a0^p0 * a1^p1 * a2^p2 ... ak^pk, 其中 a0,a1,a2...ak都是质数
3. 质数筛法: 从 2 到 n, 删除每个质数的整数倍，那么剩下的都是质数

3. 代码模板

1. 质数判断
int is_prime(int n)
{
    if(n == 1){
        return 0;
    }

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

    return 1;
}

2. 分解质因数
void divide(int n)
{
    for(int i = 2; i <= n / i; i++){
        if(n % i == 0){
            int s = 0;
            while(n % i == 0){
                n = n / i;
                s++;
            }

            printf("%d %d\n", i, s);
        }
    }
    // 注意这个点
    if(n > 1){
        printf("%d %d\n", n, 1);
    }
}

3. 筛法找质数
char st[N];
int get_primes(int n)
{
    int ans = 0;
    for(int i = 2; i <= n; i++){
        if(st[i] == 0){
            ans++;
            for(int j = i + i; j <= n; j = j + i){
                st[j] = 1;
            }
        }
    }

    return ans;
}