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