Problem 6: Smooth operator
Background:
finding smooth numbers is important in modern techniques for
cracking the RSA public key cryptosystem. A k-smooth number is a positive
integer all of whose prime factors are less than k. For our purposes
a number is smooth if it is 100-smooth.
Input:
The input will consist of positive integers, one per line,
each no more than 18 digits.
Output:
For each input number, on a line write the number
followed by the first smooth number which is strictly greater than the
input number.
Sample Input:
10
100
101
999999
1000000000000
999999999999999999
Sample Output:
10 11
100 102
101 102
999999 1000000
1000000000000 1000000006940
999999999999999999 1000000000000000000