Road Map

打怪路线：

• 判定质数：204 -> 866
• 分解质因数：
• 筛质数：欧拉筛法

质数

大于 1 的正整数，如果只包含 1 和本身两个约数，就是质数（也叫素数）

试除法判定质数

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

分解质因数

对正整数 x 分解质因数，输出 因子 和 个数

void divide_prime(int n) {
    for (int i = 2; i <= n/i; i ++ ) {
        if (n % i == 0) {
            int cnt = 0;
            while (n % i== 0)  n = n /i, cnt++;
            cout << i << ' ' << cnt << endl;
        }
    }
    if (n > 1) cout << n << ' ' << 1 << endl;
}