### 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

### 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];
for (int i = 2; i < rads.length; i++) {
for (int j = i; j < rads.length; j += i)
}
}
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 id;

public IntPair(int rads, int id) {
this.id = id;
}

public int compareTo(IntPair other) {

21417
62ms