### Semiprimes题号：187 难度： 25 中英对照

A composite is a number containing at least two prime factors. For example, 15 = 3 × 5; 9 = 3 × 3; 12 = 2 × 2 × 3.

There are ten composites below thirty containing precisely two, not necessarily distinct, prime factors: 4, 6, 9, 10, 14, 15, 21, 22, 25, 26.

How many composite integers, n < 108, have precisely two, not necessarily distinct, prime factors?

### Code

public final class p187 {
private static final int MAX_N=(int)Math.pow(10, 8)-1;
//private static final int MAX_N=30;
public static void main(String[] args){
long start=System.nanoTime();
long result = run();
long end=System.nanoTime();
System.out.println(result);
System.out.println( (end-start)/1000000 + "ms" );
}
public static long run(){
long count=0;
int[] primes=listPrimes(MAX_N/2);
int limit=(int) Math.sqrt(MAX_N);
for(int i=0;i<=limit&&i<primes.length;i++){
int end=Arrays.binarySearch(primes, MAX_N/primes[i]);
//System.out.print(end+" "+primes[i]+" ");
if(end>=0)
end++;
else{
end=-end-1;
}
if(end>i)
count+=end-i;
//System.out.println(i+" "+count);
}
return count;
}

public static int[] listPrimes(int n){
if(n<2)
return null;
List<Integer> primes=new ArrayList<>();
int[] isPrime=new int[n+1];
Arrays.fill(isPrime, 0);
int count = 0;
for (int i = 2; i*i<=n; i++){
for(int j=2*i;j<=n;j+=i){
isPrime[j]=1;
}
}
for(int i=2;i<=n;i++){
if(isPrime[i]==0){

17427258
4858ms