题解 | 几乎是质数

这题还是有点意思的

题意是让我们看看i是否只有两个不同质因数

我们可以先把i的所有质因数求出来

把它们装入set中，因为set不会有重复数字，这样最后就方便判断有几个不同的质因数了

import java.util.Scanner;
import java.util.TreeSet;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner scanner=new Scanner(System.in);
		int n=scanner.nextInt();
		int count=0;
		for (int i = 1; i <= n; i++) {
			TreeSet<Integer> set=new TreeSet<>();
			int t=i;
			while(true) {
				if(isPrime(i))break;
				for (int j = 2; j <i; j++) {
					if(t%j==0&&isPrime(j)) {
						set.add(j);
						t=t/j;
						break;
					}
				}
				if(t==1)break;
			}
			if(set.size()==2) {
				count++;
			}
		}
		System.out.println(count);

	}
	public static boolean isPrime(int n) {
		if(n<=1) {
			return false;
		}
		for (int i = 2; i <= Math.sqrt(n); i++) {
			if(n%i==0)return false;
		}
		return true;
	}

}