Problem D
Help Mr. Tomisu
Input: Standard Input
Output: Standard Output
After wasting a significant time of
his life in problem-setting, Mr. Tomisu is now
searching for glory: A glory that will make him famous like Goldbach
and rich like Bill Gates :). And he has chosen the field of Number Theory as
his prime interest. His
creator did not make him very bright and so he needs your help to solve an
elementary problem, using which he will begin his pursuit for glory!
Tomisu
has come to know that finding out numbers having large prime factors are very
important in cryptography. Given two integers N and M, he aims to count the number of integers x between 2
and N! (factorial N), having the property that all
prime factors of x are greater than M.
The input file contains at most 500 lines of inputs. Each line contains two integers N (1<N<10000001) and M (1≤M≤N and N-M≤100000). Input is terminated by a line containing two zeroes. This line should not be processed.
For each line of input produce one line of output. This line contains the value T % 100000007 (Modulo 100000007 value of T). Here T is the total number of numbers between 1 and N! (factorial N) which have prime factors greater than M.
|
100
10 100
20 10000
9000 0
0 |
43274465 70342844 39714141 |
Problemsetter: Shahriar Manzoor
Special
Thanks: Per Austrin