题解 | 几乎是质数-Java

import java.util.Scanner;
import java.util.HashSet;
import java.util.Set;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int count = 0;

        // 检查区间[1, n]中的每个数
        for (int i = 1; i <= n; i++) {
            if (isAlmostPrime(i)) {
                count++;
            }
        }

        System.out.println(count);
    }

    // 判断一个数是否是几乎是质数（恰好有两个不同的质因子）
    private static boolean isAlmostPrime(int num) {
        // 1没有质因子，不是几乎是质数
        if (num == 1) {
            return false;
        }

        Set<Integer> primeFactors = new HashSet<>();

        // 找出所有质因子
        // 先检验唯一偶质因数2，使得之后的步长可以为2
        while (num % 2 == 0) {
            primeFactors.add(2);
            num /= 2;
        }
        // 检验3及以后的因数
        for (int i = 3; i * i <= num; i += 2) {
            if (num % i == 0) {
                primeFactors.add(i);
                // 去除所有该质因子的倍数
                while (num % i == 0) {
                    num /= i;
                }
            }
        }

        // 如果剩余的数大于1，说明它本身也是一个质因子
        if (num > 1) {
            primeFactors.add(num);
        }

        // 恰好有两个不同的质因子才是几乎是质数
        return primeFactors.size() == 2;
    }
}