Time limit 4000/7000/7000/7000 ms. Memory limit 65000/65000/65000/65000 Kb.
Prepared by Ibrahim Mesecan.
kth Prime Factor of a Number
Prime factors of a number are the prime number which divides the number evenly and when you multiply all
of them you will have the number itself. For example: 12= 2x2x3. 2, 2 and 3 are the prime factors of 12.
Write a program that is going to show kth prime factor of the given number (m).
Input specification
There is one number n in the first line where 1 ≤ n ≤ 30.
Then, in the following n lines, you will be given two numbers m and k where 1 ≤ m ≤ 109
and 1 ≤ k < 15.
Output specification
Show n numbers which represent kth prime factors of the given numbers.
Note: Prime factors are assumend to be in ascending order. If k is larger than the number of prime factors of the given number, show the biggest prime factor.
If the number is prime show the number itself.
Sample Input:
5
12 3
7 1
20 10
20001 2
20000001 3
Enter a number..:
Sample Output:
3
7
5
59
952381
Output Explanation:
- Hence, prime factors of 12 are 2, 2, 3, the result is 3
- 7 is a prime number, the result is 7
- Prime factors of 20 are 2, 2, and 5. Thus, k is larger than the number of factors. The result is 5
- etc.
Для отправки решений необходимо выполнить вход.
|