Back
Close

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
FastestShortest

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
codingame x discord
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