guardian
12-02-2003, 16:56
Factorization
Problem Description
Any positive integer n (n>1) can be expressed as a product of a set of positive integers that are greater than 1, e.g., 24 = 3 * 8. Usually there is more than just one set, e.g., 24 = 4 * 6 = 2 * 12 = 2 * 2 * 6. So {4, 6}, {2, 12}, and {2, 2, 6} are another three sets. The order of elements in the set does not matter, so {2, 2, 6} is considered the same as {2, 6, 2}. (Note set is different from mathematical definition of set, as we can have duplicated items). Of course {24} is another set whose product equals to 24. Let's define a function f over all positive integer as:
f(n) = the number of different ways to factorize a integer n , if n>1
f(1) = 1
f(24) will yield 7 as there are 7 such sets: {2, 2, 2, 3}, {2, 2, 6}, {2, 4, 3}, {2, 12}, {3, 8}, {4, 6}, and {24}
Given an interval [i...j], try to find an integer n with the biggest f(n).
Input
The input consists of a few lines. Each line has two integers, i and j. They are separated by a single space. No input exceeds 1,000,000.
Output
For every line of input, print two integers n and m on one line, separated by one single space, where:
i≤n≤j, m = f(n), and n = the number that has largest number of factorizations.
If there are more than one such n, output the smallest one.
Sample Input
60 70
1000 2000
2000 3000
3000 4000
4000 5000
5000 6000
6000 7000
7000 8000
8000 9000
9000 10000
Sample Output
60 11
1440 171
2880 289
3600 269
4320 382
5760 467
6720 426
7200 484
8640 662
9600 467
Required Time : For each input, running time is not exceed 5s
-----------------------------------------------------
Bài này thì thuật toán tìm số cách factorize ra không khó, nhưng để chạy từ 1 đến 1.000.000 thì :confused:. Các bác giúp em với, đây là bài em cần nộp (thứ hai tuần sau hết hạn) :.(
Problem Description
Any positive integer n (n>1) can be expressed as a product of a set of positive integers that are greater than 1, e.g., 24 = 3 * 8. Usually there is more than just one set, e.g., 24 = 4 * 6 = 2 * 12 = 2 * 2 * 6. So {4, 6}, {2, 12}, and {2, 2, 6} are another three sets. The order of elements in the set does not matter, so {2, 2, 6} is considered the same as {2, 6, 2}. (Note set is different from mathematical definition of set, as we can have duplicated items). Of course {24} is another set whose product equals to 24. Let's define a function f over all positive integer as:
f(n) = the number of different ways to factorize a integer n , if n>1
f(1) = 1
f(24) will yield 7 as there are 7 such sets: {2, 2, 2, 3}, {2, 2, 6}, {2, 4, 3}, {2, 12}, {3, 8}, {4, 6}, and {24}
Given an interval [i...j], try to find an integer n with the biggest f(n).
Input
The input consists of a few lines. Each line has two integers, i and j. They are separated by a single space. No input exceeds 1,000,000.
Output
For every line of input, print two integers n and m on one line, separated by one single space, where:
i≤n≤j, m = f(n), and n = the number that has largest number of factorizations.
If there are more than one such n, output the smallest one.
Sample Input
60 70
1000 2000
2000 3000
3000 4000
4000 5000
5000 6000
6000 7000
7000 8000
8000 9000
9000 10000
Sample Output
60 11
1440 171
2880 289
3600 269
4320 382
5760 467
6720 426
7200 484
8640 662
9600 467
Required Time : For each input, running time is not exceed 5s
-----------------------------------------------------
Bài này thì thuật toán tìm số cách factorize ra không khó, nhưng để chạy từ 1 đến 1.000.000 thì :confused:. Các bác giúp em với, đây là bài em cần nộp (thứ hai tuần sau hết hạn) :.(