Multiples of Primes

Interview

Time limit0.25sMemory limit512 MB

Summary

Given up to 10 distinct primes and a limit M up to 1e12, count the natural numbers at most M divisible by at least one listed prime.

Level: Medium7 of 10
Topics: Combinatorics, Math, Number theory, Bit manipulation
Solved: No attempts yet

Problem

You are given $N$ primes and a natural number $M$ . Among the natural numbers not exceeding $M$ , count how many are divisible by at least one of the $N$ primes.

Input

The first line contains $N$ ( $1 \le N \le 10$ ) and $M$ ( $1 \le M \le 10^{12}$ ). The second line contains $N$ primes. Each given prime is at most $100$ , and no prime appears more than once.

Output

Print the number of natural numbers not exceeding $M$ that are divisible by at least one of the $N$ primes.

Examples5

Example 1
Input
```
1 100
3
```
Expected output
```
33
```
Example 2
Input
```
2 100
2 3
```
Expected output
```
67
```
Example 3
Input
```
3 100
2 3 5
```
Expected output
```
74
```
Example 4
Input
```
4 100
2 3 5 7
```
Expected output
```
78
```
Example 5
Input
```
5 100
11 13 17 19 23
```
Expected output
```
30
```