## 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!
Online Participants