SmoothNumbers
SRM 388 · 2008-01-15 · by bmerry
SRM 388 · 2008-01-15 · by bmerry · Brute Force, Simple 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 100,000, inclusive.
- k will be between 1 and 100, inclusive.
Examples
0)
10 3 Returns: 7
Of the first ten integers, only 5, 7 and 10 have prime factors greater than 3.
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)
100000 100 Returns: 17442
Submissions are judged against all 26 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class SmoothNumbers with a public method int countSmoothNumbers(int N, int k) · 26 test cases · 2 s / 256 MB per case