The Prime Roommates

3.8

10 votes
Medium
Problem

Vikrant and Sarthak are roommates and this morning they had a fight over who is smarter.As we all know Sarthak is a geek so he gave Vikrant a task, he gave him a number N and asked that how many good number we can produce using prime numbers less than or equal to N.

According to Sarthak , we can define a good number as product of two distinct prime numbers. G=AxB is good if and only if *A is prime and *B is prime and A!=B **.

Vikrant tried hard but could not get the answer but he also don't wanna get kicked out of room so he asked you for help to complete the task.

INPUT

The first line of input contains a single integer N.

1<=N<=10^7

OUTPUT

Print number of *good numbers * we can produce using prime numbers less than or equal to N.

Sample Input
10
Sample Output
6
Time Limit: 1
Memory Limit: 256
Source Limit:
Editor Image

?