How to optimise this code for N=10^12.

Question

This is for finding the factors of N numbers .
https://code.sololearn.com/c1orm62MH0zb/?ref=app

input
2 //no. of test cases
10
64

output
4
7

Answer 1

Write question more clearly.

Do you want to count the number of factors of a big number?

If so, you can use a trick that if N%i == 0 then N has two factors: i and N/i. But you should not count N/i if it is equal to i. i must iterate from 1 to square root of N.

The code that calculate number of factors of one big number will be something like this:

unsigned number_of_factors(long long num)
{
unsigned count = 0;
for(long long int i = 1; i * i <= num; ++i){
if(num % i == 0){
++count;
if(i != num / i) ++count;
}
}
return count;
}

Answer 2

If you want to find the factors of a single large number I agree with what andriy kan said. That'll be 10^6 numbers to check which should be fast.

If you have to check 10^12 numbers on the order of 10^12 I would probably use an efficient algorithm for finding all prime factors of a number (like the quadratic sieve algorithm) and use those to find the total number of factors.

Answer 3

How large are those 10^12 numbers?

Answer 4

Schindlabua
1<=N<=10^12