0
How to optimise this code for N=10^12.
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
4 Respuestas
+ 3
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;
}
+ 1
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.
0
How large are those 10^12 numbers?
0
Schindlabua
1<=N<=10^12