SmoothNumbers | Topcoder Archive

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
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.