What is the fastest way to compute all factors of a number efficently?

help
1

What is the efficient way to find all factors of a number?

PS: I am using a prime sieve, storing least prime factor of each no in sieve array and after then dividing each no by prime_factor[number] ( storing it in the map ) and at the same time dividing the number by prime_factor[number] while it is not equal to 1.
I know it is wrong to approach as so many factors are missing.

Please suggest some good approaches.

2

For finding factors run loop from i=2 to sqrt(n). If i divides n then n/i will also divide. Also check that they are equal or not. This will be done in O(sqrt(n))

1 Like
3

That I know I wanted O(logN) apporach as at the same time I have perform some Queries .

4

Do you need to find prime factorization?

5

No all factors of number

6

I think for finding all factors of a number that will be the fastest approach. But for prime factors it can be done in O(lgn)

7 
 vector <int> vec(0);
 for (int i = 1; i*i <= n; ++i)
 {
     if (n % i == 0)
     {
         vec.push_back(i);
         vec.push_back(n/i);
     }
}

This is how you get the factors of a number in O(\sqrt{n}). The idea is that if i | n, \dfrac{n}{i} | n. That’s why we only need \sqrt{n} iterations.
On a side note, in today’s codeforces division 3 round, problem D could only be solved with this method rather than the naive O(n) method due to the constraints :slight_smile:

8

You aren’t checking if i == n/i for factors such as 4 for 16.

9

I know. That is a slight modification. Thanks anyway.

10

Maybe this could help

11

What will be the time comp of the recursion part?