5. Odd number of divisors - solution

Method I: Brute force

This method checks all numbers in the interval from a to b one by one. A separate function determines how many divisors each of these numbers has, and if that number is odd, a counter initialized to 0 is increased by 1 every time we find a number with an odd number of divisors. Solution:#include <iostream>

using namespace std;
/*
Example 1
Input
3 12
Output
2
Explanation of the example: The divisors of the numbers from 3 to 12 are:
3: 1, 3
4: 1, 2, 4
5: 1, 5
6: 1, 2, 3, 6
7: 1, 7
8: 1, 2, 4, 8
9: 1, 3, 9
10: 1, 2, 5, 10
11: 1, 11
12: 1,2,3,4,6,12
We can see that in total two numbers (4 and 9) have an odd number of divisors
*/


uint64_t number_of_divisors(uint64_t a)
{
uint64_t count=0;
for(uint64_t d=1; d<=a; d++)
    {
if(a%d==0)
        {
  //      cout <<d<<endl;
            count++;
        }
    }
return count;
}
int main()
{
uint64_t a,b,count=0;
cin>>a>>b;

/*Changes the current number in the interval from a to b*/
for(uint64_t i=a; i<=b; i++)
    {
uint64_t b=number_of_divisors(i); //Computes the number of divisors of the current number
if(b%2 != 0) //If the number of divisors is odd
        {
            count++; //Increases the counter by 1
        }
    }

cout<<count;
return 0;
}

This solution is quite inefficient for larger values, which according to the task can be up to 215
A much more efficient solution is shown below:

Solution II: The function perfect_square

This solution is based on the fact that only "perfect squares" have an odd number of divisors.
Prime numbers have only two divisors, 1 and the number itself, e.g. the divisors of 7 are 1 and 7, so there are two of them, which is an even number.
Other numbers that are not perfect squares also have an even number of divisors. In Figure 1 you can compare the numbers 12 and 16. The first one is not a perfect square, and you can see that besides 1 and 12, colored orange, there are pairs of divisors whose product is 12. These are e.g. 2 and 6 (blue), 3 and 4 (green). So there is always an even number of divisors. Unlike numbers that are not perfect squares, for a number such as 16 you can notice that almost all divisors have their pairs whose product is 16, just like in the previous case, but the divisor 4 would be paired with itself, i.e. 4*4=16. Since we count that divisor only once, we can conclude that perfect squares have an odd number of divisors. This is explained in more detail in the lesson: Prime numbers and factorization.
​Finding the divisors of numbers. A non-square and a perfect square.
Figure 1: Finding the divisors of numbers. A non-square and a perfect square.
Below is a solution in which, instead of a function that finds the number of divisors of a number, we have a function that returns whether the current number is a "perfect" square or not. In the main function, a loop changes the current number to be checked in the interval from a to b. The counter increases only when we find a number that is a perfect square. The solution is given below:#include <iostream>
#include<cmath>
using namespace std;
/*
Example 1
Input
3 12
Output
2
Explanation of the example: The divisors of the numbers from 3 to 12 are:
3: 1, 3
4: 1, 2, 4
5: 1, 5
6: 1, 2, 3, 6
7: 1, 7
8: 1, 2, 4, 8
9: 1, 3, 9
10: 1, 2, 5, 10
11: 1, 11
12: 1,2,3,4,6,12
20: 1,2, 4,5,10, 20
16: 1 2 4 8 16
We can see that in total two numbers (4 and 9) have an odd number of divisors
*/

/*Function that checks whether the number a is a perfect square*/
bool perfectSquare(uint64_t a)
{
bool result=false; //Assume it is not a perfect square
if(a>0){
uint64_t b=sqrt(a);
        result=(b*b==a);//logical expression whose value is assigned to the variable result
    }
return result;
}
int main()
{
uint64_t a,b,count=0;
cin>>a>>b;
   /*Changes the current number i in the interval from a to b with step 1*/
for(uint64_t i=a; i<=b; i++)
    {
/*Checks whether it is a perfect square*/
if(perfectSquare(i))
        {
            count++;
        }
    }

cout<<count;
return 0;
}

Conclusion

Using a loop from a to b is inefficient, especially when the range is large (up to 1015). A solution that checks every number would be too slow. Instead, a mathematical approach should be used to compute the number of perfect squares in the range directly. Here is the corrected solution:


Solution 3: Fully optimized solution

Here there is only the main function. Optimized solution in the main function:



#include <iostream>
#include <cmath>

using namespace std;


int main() {
uint64_t a, b, count = 0;
cin >> a >> b;

// Finding the first and the last perfect square in the range
uint64_t firstRoot = ceil(sqrt(a));
uint64_t lastRoot = floor(sqrt(b));

// Counting the perfect squares between a and b
if (firstRoot <= lastRoot) {
        count = lastRoot - firstRoot + 1;
    }

cout << count << endl;

return 0;
}

Conclusion

This code is efficient and solves the problem with a mathematical approach instead of iterating through a large range of numbers, which makes it suitable for working with large numbers up to 1015