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

general
#1

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
#2

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.

#3

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

#4

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

2 Likes
#5

@gjaiswal108 You solved it bro …??

#6

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

#7

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

#8

@gogetassj4 Kind of same with Fast I/O

#9

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

#10

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

#11

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
#12

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

#13

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

#14

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++.

#15

@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:

#16

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++

#17

hope there is no ambiguity…

#18


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

1 Like
#19

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

#20

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.