几乎是质数

思路

题目在说什么？给定正整数 ，求区间 中恰好有两个不同质因子的数的个数。比如 有两个不同质因子，是"几乎是质数"； 只有一个质因子，不算； 有三个，也不算。

那怎么高效统计每个数有多少个不同的质因子呢？

关键观察

暴力对每个数做质因数分解是 ，太慢。换个角度想：与其"对每个数找它的质因子"，不如对每个质数，标记它是谁的因子。

这就是埃氏筛的思路：枚举每个质数 ，把 这些倍数的"不同质因子计数"都加 1。筛完之后，计数恰好为 2 的就是答案。

怎么判断 是质数？如果 还没被任何更小的质数标记过（计数为 0），那它就是质数。

具体做法

  1. 开一个数组 cnt[i]，表示 的不同质因子个数，初始为 0
  2. 从 遍历到 ，如果 cnt[i] == 0，说明 是质数，遍历它的所有倍数 ，令 cnt[j]++
  3. 最后统计 cnt[i] == 2 的个数

代码

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n;
    scanf("%d", &n);
    vector<int> cnt(n + 1, 0);
    for(int i = 2; i <= n; i++){
        if(cnt[i] == 0){
            for(int j = i; j <= n; j += i){
                cnt[j]++;
            }
        }
    }
    int ans = 0;
    for(int i = 2; i <= n; i++){
        if(cnt[i] == 2) ans++;
    }
    printf("%d\n", ans);
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] cnt = new int[n + 1];
        for (int i = 2; i <= n; i++) {
            if (cnt[i] == 0) {
                for (int j = i; j <= n; j += i) {
                    cnt[j]++;
                }
            }
        }
        int ans = 0;
        for (int i = 2; i <= n; i++) {
            if (cnt[i] == 2) ans++;
        }
        System.out.println(ans);
    }
}

import sys

def solve():
    n = int(sys.stdin.readline())
    cnt = [0] * (n + 1)
    for i in range(2, n + 1):
        if cnt[i] == 0:
            for j in range(i, n + 1, i):
                cnt[j] += 1
    ans = 0
    for i in range(2, n + 1):
        if cnt[i] == 2:
            ans += 1
    print(ans)

solve()

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', line => lines.push(line));
rl.on('close', () => {
    const n = parseInt(lines[0].trim());
    const cnt = new Int32Array(n + 1);
    for (let i = 2; i <= n; i++) {
        if (cnt[i] === 0) {
            for (let j = i; j <= n; j += i) {
                cnt[j]++;
            }
        }
    }
    let ans = 0;
    for (let i = 2; i <= n; i++) {
        if (cnt[i] === 2) ans++;
    }
    console.log(ans);
});

复杂度分析

  • 时间复杂度：，和埃氏筛一样，每个质数 遍历 个倍数，质数倒数和为
  • 空间复杂度：，存储质因子计数数组

总结

这道题的核心是把"统计每个数的不同质因子个数"转化为埃氏筛的变体。标准的埃氏筛是标记合数，这里改成对每个质数的倍数做计数累加。筛完后扫一遍数组，计数为 2 的就是"几乎是质数"。思路简洁，代码也很短。