fastest method to find all divisors

Jun 1, 2009 at 7:10pm
i need to find the all the divisors of a num(int) i am applying this approach
for(int i=1;i<=n/2;i++)}
if(n%i==0) v.push_back(i);
}
here vector v will return all the divisors of input number n
but this is quite slow method can anyone please suggest me a faster approach to do this job
thanks

Jun 1, 2009 at 7:19pm
Try i<=sqrt(n).

EDIT: You can also speed up insertion time by calling v.reserve(sqrt(n)) before the loop.
Last edited on Jun 1, 2009 at 7:21pm
Jun 1, 2009 at 7:33pm
u mean using i<=sqrt(n) in for loop but what does v.reserve(sqrt(n)) do?

Jun 1, 2009 at 7:50pm
Vectors have two sizes: size and capacity. Each push_back() increases the size by one and assigns the parameter to the tail of the vector. The capacity if the physical size of the array. If at the time of the push_back() the size is the same as the capacity, the vector has to create a larger array, copy the original to the new, and destroy the original. This is quite expensive. If you reserve an appropriate number of elements at the start, push_back() will only need to reallocate until the size reaches the capacity. If you reserve enough, push_back() never need to reallocate.

I was wrong. You should reserve sqrt(n)*2 and at each loop you should push_back() i and n/i. Note that this will result in an unsorted vector but it's the fastest method I can think of to find all divisors. It takes only O(n1/2) time.
Last edited on Jun 1, 2009 at 7:57pm
Jun 1, 2009 at 7:55pm
this method will not work as i am tring to find all the divisors of input number either prime or composite
Jun 1, 2009 at 7:57pm
let say input no is 12 then all divisors are 1,2,3,6(not taking 12 into account)
while sqrt(12) is around 3 so it will miss 6
Jun 1, 2009 at 8:00pm
The method should work to tell those apart. However, you shouldn't use it to find primes, since on average it takes more iterations to find all the divisors of a number than to check if the number is prime.

EDIT:
n=12
(int)sqrt(12)=3
12%1==0, so 1 and 12, because 12/1==12
12%2==0, so 2 and 6, because 12/2==6
12%3==0, so 3 and 4, because 12/3=4
Done.
Last edited on Jun 1, 2009 at 8:02pm
Jun 1, 2009 at 8:04pm
whoooa!!!!
how stupid i am ^^
thanks and sorry for makink u post such silly think for me :D
Topic archived. No new replies allowed.