Problem Statement
A positive integer is said to be k-smooth if its largest prime factor is no greater than k. Compute how many positive integers less than or equal to N are k-smooth.
Definition
- Class:
- SmoothNumbers
- Method:
- countSmoothNumbers
- Parameters:
- int, int
- Returns:
- int
- Method signature:
- int countSmoothNumbers(int N, int k)
- (be sure your method is public)
Constraints
- N will be between 1 and 100,000, inclusive.
- k will be between 1 and 100, inclusive.
Examples
10
3
Returns: 7
Of the first ten integers, only 5, 7 and 10 have prime factors greater than 3.
10
4
Returns: 7
4 is not prime, so 4-smooth numbers are the same as 3-smooth numbers.
15
3
Returns: 8
5
20
Returns: 5
100000
100
Returns: 17442
1
1
Returns: 1
1
100
Returns: 1
100000
1
Returns: 1
2
2
Returns: 2
99999
100
Returns: 17441
99999
96
Returns: 16760
99999
97
Returns: 17441
96
97
Returns: 96
96
96
Returns: 96
121
11
Returns: 61
168
13
Returns: 87
50
7
Returns: 31
50000
10
Returns: 566
65536
2
Returns: 17
2
1
Returns: 1
99999
1
Returns: 1
100000
4
Returns: 101
10
1
Returns: 1
100
1
Returns: 1
1000
1
Returns: 1
15
1
Returns: 1