Print All Divisors of Number in Increasing Order (Code Vita)

We have to basically print all divisors of a given number N in increasing order .

I have used square root method which has complexity of O(sqrt(N)) but it gives TLE

Constrains is
T = 15
1<= N <=10^15

What should be approach for this problem …??

1 Like

N is 10^15 so time will be O(10^7.5) (less then O(10^8)) shouldn’t this pass the time limit? I Haven’t heard of a better algorithm… Make sure you are using fast io.

there is also T=15, N<=10^15

TCS made this year a new algo(If it was not in the existence till now :smile:)

2 Likes

@gjaiswal108 You solved it bro …??

Nope bro,It was a nightmare for me…waiting for the editorial. :sweat_smile:

You did this? https://www.geeksforgeeks.org/find-all-divisors-of-a-natural-number-set-2/

@gogetassj4 Kind of same with Fast I/O

It should work then, if it timed out then I’d probably use array to store the bigger ones instead of vector.

If someone’s solution got accepted, please post it here.
I’m actually desperate to see the solution

Can I submit that que now ?? If yes then send me link.
I think precompute primes till sqrt(10^15) using sieve and then for each test cases just find which prime factors divides it.
And then find power of those prime factors.
And then find all possible divisors.
Here t=15 hence we need to reduce complexity by 15 at least. Which can be done by finding prime numbers.

2 Likes

@l_returns Ya i thought of same , but how should we efficiently get all divisors from prime factors …??

That’s basic recursion. If we have 5 prime factors then we will have 5 nested for loops. Instead we can use recursion to make 5 nested for loops
We will have 12-13 prime factors at most

I was thinking about the same but I think memory limit will be exceeded. Sqrt(10^15) is a bit too much, atleast for C++.

@l_returns Can you please provide code or pseudo code for finding all divisors from powers of prime factors, it will help alot :slight_smile:

Should not exceed :thinking:
Other you won’t be able to store divisors as well because divisors will be O(2*sqrt(N))
And at least codechef allows array upto size 10^8 if you declare globally in c++

hope there is no ambiguity…


Check this.
If you still don’t get it ping me.

1 Like

No, upperbound of divisors of a number can be atmost n^1/3, so for n=10^15, max divisors can be 10^5 which can be stored easily

Suppose N=40; it has two prime factor 2,5. How can u generate with recursion/loop all it’s factors.
Ps: 20 is also a factor of it. Using loop how can u get 20 with 2 and 5.
So storing just prime factor won’t work.