当前位置:首页 » Project Euler » 详细页

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?

Solution

题意要求所有小于等于10^8-1的数中,可且仅可分解成两个质数乘积的数的个数 因此解题思路分为两步,为方便解释,下设$$MAXN=10^8-1$$ - 求小于等于MAX_N的数中所有的质数,进一步思考,由于最小的质数为2,那么最后满足的两个质数乘积小于等于MAXN的质数,只要满足$$prime<=\frac{MAXN}{2}$$即可 该步骤的具体思路如下,设$$n=\frac{MAXN}{2}$$ ① 将[2,n]区间中的数不是质数的标为1(可依次将2的倍数,3的倍数……标记) ② 将[2,n]区间中是质数的数组成数组primes返回 - 求可且仅可分解成两个质数乘积的数的个数 该步骤的具体思路如下 ① 遍历primes,找出与primes[i]乘积最接近MAXN的质数的index 这里要说明Arrays.binarySearch这个函数,如果要找的数在该数组中,返回该数的索引值end,否则返回-(插入点+1),所以当返回值小于0时,$$end=-(end+1)$$ 在返回的索引值之前的primes与该质数的乘积都小于MAX_N(注意end-i包括了该质数与本身的乘积) ② 当end>i时,$$count+=end-i$$

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){
        		primes.add(i);
        	}
        }
        int[] ans=new int[primes.size()];
        for(int i=0;i<primes.size();i++){
        	ans[i]=primes.get(i);
        }
        return ans;

	}
}
17427258
4858ms