## Almost prime numbers

Statement

A number is called almost prime if it has exactly two different prime divisors. For example, the numbers 6, 18, 24 are almost prime, and 4, 8, 9, 42 are not. Find the number of almost prime numbers from 1 to n inclusive.

Input description

The first line of the input file contains the number n (1 ≤ n ≤ 3000).

Output description

Print the number of almost prime numbers from 1 to n inclusive.

Constraints

This is a realization problem: for each number from 1 to n, we decompose it into prime factors and calculate the number of different prime factors.

Game modes

Fastest

Test cases

Test 1 Test

Input

1

Output

0

Validator 1 Validator

Input

222

Output

125

Test 2 Test

Input

2

Output

0

Validator 2 Validator

Input

8

Output

1

Test 3 Test

Input

3

Output

0

Validator 3 Validator

Input

19

Output

6

Test 4 Test

Input

4

Output

0

Validator 4 Validator

Input

77

Output

41

Test 5 Test

Input

10

Output

2

Validator 5 Validator

Input

3000

Output

1375

Test 6 Test

Input

2000

Output

958

Validator 6 Validator

Input

2999

Output

1375

Test 7 Test

Input

1000

Output

508

Validator 7 Validator

Input

2998

Output

1375

Solution language

Solution

Stub generator input

Join the CodinGame community on Discord to chat about puzzle contributions, challenges, streams, blog articles - all that good stuff!

JOIN US ON DISCORD Online Participants