SmoothNumbersHard
SRM 388 · 2008-01-15 · by bmerry
SRM 388 · 2008-01-15 · by bmerry · Math
Problem Statement
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.
Constraints
- N will be between 1 and 5,000,000, inclusive.
- k will be between 1 and 1,000, inclusive.
Examples
0)
10 3 Returns: 7
Of the first ten positive integers, only 5, 7 and 10 have prime factors greater than 3; the rest are 3-smooth.
1)
10 4 Returns: 7
4 is not prime, so 4-smooth numbers are the same as 3-smooth numbers.
2)
15 3 Returns: 8
3)
5 20 Returns: 5
4)
5000000 1000 Returns: 1196525
Submissions are judged against all 45 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class SmoothNumbersHard with a public method int countSmoothNumbers(int N, int k) · 45 test cases · 2 s / 256 MB per case