We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.

Loading...

- All Contests
- ProjectEuler+
- Project Euler #193: Squarefree Numbers

# Project Euler #193: Squarefree Numbers

# Project Euler #193: Squarefree Numbers

A positive integer is called squarefree, if no square of a prime divides , thus are squarefree, but not .

Similarly, let us define a positive integer to be powerfree if no power of a prime divides . For example, is powerfree, but not .

You are given two positive integers, , and . Find the number of powerfree positive integers

**Input Format**

The only line of the input contains two integers, , and .

**Constraints**

**Output Format**

Print one line containing the number of powerfree positive integers

**Sample Input 0**

```
10 2
```

**Sample Output 0**

```
7
```

**Explanation 0**

We have to find the number of -powerfree (squarefree) integers . These integers are

**Sample Input 1**

```
10 3
```

**Sample Output 1**

```
9
```

**Explanation 1**

All positive integers are -powerfree, except . (Since is divisible by )