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

Ordered radicals 题号:124 难度: 25 中英对照

The radical of n, rad(n), is the product of the distinct prime factors of n. For example, 504 = 23 × 32 × 7, so rad(504) = 2 × 3 × 7 = 42.

If we calculate rad(n) for 1n ≤ 10, then sort them on rad(n), and sorting on n if the radical values are equal, we get:

Unsorted

Solution

1. i从1-10000,计算出rad(i)。 rad(i)是i的互异质因数的乘积。在计算rad(i)的时候,依次与因数相乘即可。 2. 对[rad,id]排序。 在这里,新定义了一个整数对类IntPair,把[rad,id]作为一个整数对,对这个整数对进行排序。

Code

import java.util.Arrays;

public class p124 {
	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" );
	}
	private static final int LIMIT = 100000;
	
	public static long run() {
		int[] rads = new int[LIMIT + 1];
		Arrays.fill(rads, 1, rads.length, 1);
		//计算rads
		for (int i = 2; i < rads.length; i++) {
			if (rads[i] == 1) {
				for (int j = i; j < rads.length; j += i)
					rads[j] *= i;
			}
		}
		//data存放[rads(id),id]这个整数对
		IntPair[] data = new IntPair[LIMIT];
		for (int i = 0; i < data.length; i++)
			data[i] = new IntPair(rads[i + 1], i + 1);
		Arrays.sort(data);//排序
		return data[10000 - 1].id;//序号从0开始,因此第10000个整数对的序号是9999
	}
	
	
	//整数对类
	private static final class IntPair implements Comparable<IntPair> {
		
		public final int rads;
		public final int id;
		
		
		public IntPair(int rads, int id) {
			this.rads = rads;
			this.id = id;
		}
		
		
		public int compareTo(IntPair other) {
			if (rads != other.rads)
				return Integer.compare(rads, other.rads);
			else
				return Integer.compare(id, other.id);
		}
		
	}
}
21417
62ms