- All Contests
- ProjectEuler+
- Project Euler #234: Semidivisible numbers

# Project Euler #234: Semidivisible numbers

# Project Euler #234: Semidivisible numbers

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

For an integer , we define the lower prime square root of , denoted by , as the largest prime and the upper prime square root of , , as the smallest prime .

So, for example, , , .

Let us call an integer semidivisible, if one of and divides , but not both.

The sum of the semidivisible numbers not exceeding is , the numbers are , and .

is not semidivisible because it is a multiple of both and .

As a further example, the sum of the semidivisible numbers up to is .

Given two integers and , what is the sum of all semidivisible numbers ? Print your answer modulo .

**Input Format**

The only line of each test file contains two space-separated integers: and .

**Constraints**

- .
- .

**Output Format**

Print the answer modulo .

**Sample Input 0**

```
4 15
```

**Sample Output 0**

```
30
```

**Explanation 0**

There are three semidivisble integers : , and .

**Sample Input 1**

```
10 45
```

**Sample Output 1**

```
290
```

**Explanation 1**

The only semidivisble integers : are , , , , , , , , , and .

**Sample Input 2**

```
100 150
```

**Sample Output 2**

```
708
```

**Explanation 2**

The only semidivisble integers are: , , , , and .