- All Contests
- ProjectEuler+
- Project Euler #204: Generalised Hamming Numbers

# Project Euler #204: Generalised Hamming Numbers

# Project Euler #204: Generalised Hamming Numbers

_{This problem is a programming version of Problem 204 from projecteuler.net}

A Hamming number is a positive number which has no prime factor larger than .

So the first few Hamming numbers are , , , , , , , , , , .

There are Hamming numbers not exceeding .

We will call a positive number a generalised Hamming number of type , if it has no prime factor larger than .

Hence the Hamming numbers are the generalised Hamming numbers of type .

How many generalised Hamming numbers of type are there which don't exceed ?

**Input Format**

The only line of each test file contains two integer numbers separated by a single space: and .

**Constraints**

**Output Format**

Print exactly one number: the number of generalised Hamming numbers of type which don't exceed .

**Sample Input 0**

```
15 5
```

**Sample Output 0**

```
11
```

**Explanation 0**

These eleven are "the first few Hamming numbers" from the problem statement.

**Sample Input 1**

```
100000000 5
```

**Sample Output 1**

```
1105
```