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

Consecutive positive divisors 题号:179 难度: 25 中英对照

Find the number of integers 1 < n < 107, for which n and n + 1 have the same number of positive divisors. For example, 14 has the positive divisors 1, 2, 7, 14 while 15 has 1, 3, 5, 15.

Solution

题目要求输出从1-10^7中和下一个数约数个数相同的数的个数 求解重点在于如何求出每个数的约数个数 容易想到对每个数求它的约数,然后统计个数,但是这样很慢 比较快的方法如下: - 首先,每个数(除了1)都有1和自己本身两个约数,初始设为2 - 接着,将所有是2倍数的数,约数个数+1,这些数是$$2\times2,2\times2+2,2\times2+2+2...$$ - 接着,将所有是3倍数的数,约数个数+1,这些数是$$2\times3,2\times3+3,2\times3+3+3...$$ ... 最后就能求得这个范围内所有数的约数的个数 在实现时,可使用两层for循环,第一层表明当前的约数,第二层表示该约数的倍数

Code

import java.util.Arrays;
public final class p179 {
	private static final int MAX_N=(int) Math.pow(10, 7);
	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(){
		int[] num=new int[MAX_N];
		Arrays.fill(num, 2);
		for(int i=2;i<num.length;i++){
			for(int j=2*i;j<num.length;j=j+i){
				num[j]++;
			}
		}
		long count=0;
		for(int i=2;i<num.length-1;i++){
			//System.out.println(i+"="+num[i]);
			if(num[i]==num[i+1]){
				count++;
			}
		}
		return count;
	}
}
986262
1823ms