Odd number of divisors
Statement
Goal
Output the number of integers between a and b (inclusive) which have an odd number of unique divisors.Efficient approach is required for the 2 last cases.
Example for a=1 and b=4:
1 has only 1 divisor (1) => Odd number of divisors
2 has 2 divisors (1,2) => Even number of divisors
3 has 2 divisors (1,3) => Even number of divisors
4 has 3 divisors (1,2,4) => Odd number of divisors
So 1 and 4 have an odd number of divisors.
The output expected is 2.
Input
Line 1: Two space-separated positive integers a b
Output
The number of integers between a and b (inclusive) which have an odd number of unique divisors.
Constraints
0 < a < b < 10^6
Example
Input
1 4
Output
2
Game modes
Fastest, Shortest
Test cases
Test 1 Test
Input
1 4
Output
2
Validator 1 Validator
Input
1 8
Output
2
Test 2 Test
Input
1 12
Output
3
Validator 2 Validator
Input
1 16
Output
4
Test 3 Test
Input
16 25
Output
2
Validator 3 Validator
Input
9 25
Output
3
Test 4 Test
Input
25 900
Output
26
Validator 4 Validator
Input
36 10000
Output
95
Test 5 Test
Input
8 3601
Output
58
Validator 5 Validator
Input
50 3999
Output
56
Test 6 Test
Input
1 10000
Output
100
Validator 6 Validator
Input
4 10000
Output
99
Test 7 Test
Input
1 250000
Output
500
Validator 7 Validator
Input
9 250000
Output
498
Solution language
Solution
Stub generator input