Indivisibility
Contest: Experimental Educational Round: VolBIT Formulas Blitz
Difficulty rating: 1500
Tags: math, number theory

IT City company developing computer games decided to upgrade its way to reward its employees. Now it looks the following way. After a new game release users start buying it actively, and the company tracks the number of sales with precision to each transaction. Every time when the next number of sales is not divisible by any number from 2 to 10 every developer of this game gets a small bonus.

A game designer Petya knows that the company is just about to release a new game that was partly developed by him. On the basis of his experience he predicts that n people will buy the game during the first month. Now Petya wants to determine how many times he will get the bonus. Help him to know it.

Input format:
The only line of the input contains one integer n (1 ≤ n ≤ 1018) — the prediction on the number of people who will buy the game.

Output format:
Output one integer showing how many numbers from 1 to n are not divisible by any number from 2 to 10.

Constraints:
Time limit: 0.5 s
Memory limit: 64.0 MB

Example input:
12

Example output:
2

Editorial:
The amount of numbers from 1 to n not divisible by any number from 2 to 10 is equal to the amount of all numbers from 1 to n (that is n) minus the amount of numbers from 1 to n divisible by some number from 2 to 10.
The set of numbers from 1 to n divisible by some number from 2 to 10 can be found as union of the set of numbers from 1 to n divisible by 2, the set of numbers from 1 to n divisible by 3 and so on till 10.
Note that sets of numbers divisible by 4 or 6 or 8 are subsets of the set of numbers divisible by 2, and sets of numbers divisible by 6 or 9 are subsets of the set of numbers divisible by 3. So there is no need to unite 9 sets, it is enough to unite sets for 2, 3, 5, 7 only.
The size of set of numbers from 1 to n divisible by some of 2, 3, 5, 7 can be calculated using inclusion-exclusion principle that says that size of each single set should be added, size of pairwise intersections should be subtracted, size of all intersections of three sets should be added and so on.
The size of set of numbers from 1 to n divisible by 2 is equal to $$\left\lfloor \frac{n}{2} \right\rfloor$$, the size of set of numbers from 1 to n divisible by 2 and 3 is equal to $$\left\lfloor \frac{n}{2 \cdot 3} \right\rfloor$$ and so on.
The final formula is $$n - \left\lfloor \frac{n}{2} \right\rfloor - \left\lfloor \frac{n}{3} \right\rfloor - \left\lfloor \frac{n}{5} \right\rfloor - \left\lfloor \frac{n}{7} \right\rfloor + \left\lfloor \frac{n}{2 \cdot 3} \right\rfloor + \left\lfloor \frac{n}{2 \cdot 5} \right\rfloor + \left\lfloor \frac{n}{2 \cdot 7} \right\rfloor + \left\lfloor \frac{n}{3 \cdot 5} \right\rfloor + \left\lfloor \frac{n}{3 \cdot 7} \right\rfloor + \left\lfloor \frac{n}{5 \cdot 7} \right\rfloor - \left\lfloor \frac{n}{2 \cdot 3 \cdot 5} \right\rfloor - \left\lfloor \frac{n}{2 \cdot 3 \cdot 7} \right\rfloor - \left\lfloor \frac{n}{2 \cdot 5 \cdot 7} \right\rfloor + \left\lfloor \frac{n}{2 \cdot 3 \cdot 5 \cdot 7} \right\rfloor$$
Division with rounding down in the formula in a programming language is usually just integer division.