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

21st Feb 2020, 5:23 AM
Hima
Hima - avatar
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; }
21st Feb 2020, 6:57 AM
andriy kan
andriy kan - avatar
+ 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.
21st Feb 2020, 7:42 AM
Schindlabua
Schindlabua - avatar
0
How large are those 10^12 numbers?
21st Feb 2020, 6:50 AM
Schindlabua
Schindlabua - avatar
0
Schindlabua 1<=N<=10^12
21st Feb 2020, 6:56 AM
Hima
Hima - avatar