Finding all factors of a number

See complete series on maths problems here:
In this lesson, we will see an efficient algorithm to find out all the factors of a given natural number.
Pre-requisite: basic understanding of loops and knowledge of how to analyze time complexity of algorithms.

[mycodeschool]

As i said earlier, this is a thing of practice. You need to pick up a large variety of problems and study them. You need to know about all kind of algorithm design techniques and how to analyze them. That's when patterns set into your mind. A good way to grow and build skillls is participating in algorithm competitions on sites like Topcoder.

[mycodeschool]

Hi Jose,
There are patterns in mathematical and algorithmic problems. If you see, one pattern sometimes forms the basis of more than one algorithm. When we study these efficient algorithms, these patterns set into our mind and improve our logical ability in trying to decode other problems. So, the only trick is -solve a lot of problems. This question is like, lifting weight bothers me, will i ever be a body builder? Start with light weights and your will soon be good to lift large ones.

[ratkapna]

When you said that you would leave the implementation where we would have sorted array of factors, did you mean without changing the complexity? The only idea that comes to my mind is this - let's use an example of factors of 36 the way we would get them in this algorithm:
1 36 2 18 3 12 4 9 6
Let's create a new empty array B. It is easy to see that if we started from the element at the position 0 and took every 2nd element from there (so the set of indices would be S = { 0, 2, 4, 6, ... 2*k }), added them to the array B, and then went from the other side of the array, starting at the last element (if sqrt(n) is not a factor of n), otherwise the second last element (let's denote that element as j-th), and added every (j - 2*k)th element to the array (where j - 2*k >= 0), we would get a sorted array B of factors of N.
This is O(sqrt(N)) solution (since there are at most 2*sqrt(N) factors) which does not change the complexity, but requires extra O(sqrt(N)) memory.
I also have an idea of an in-place algorithm (no extra memory required) which would iterate through the array 2 times and do necessary swaps, but it is not that elegant... Here's the pastie of what it would look like:

My question is: Is there a better way to do this, i.e. WHILE finding the factors?

For a sorted list (i'm working with c++) in the condition "i != sqrt(n)" i used a stack to save all those elements (including first the "n" number) and i added to the list at the end of the program

[simran]

There is no need to store these numbers, you can just print while checking if condition in the for loop for example:
#include<iostream>
#include<math.h>
using namespace std;
int main(){
int num;
cout<<"enter a number=";
cin>>num;
cout<<"factors of a number are=";
for(int i=1;i<=sqrt(num);i++){
if(num%i==0)
cout<<i<<" ";
}
for(int i=sqrt(num);i>=1;i--){
if(num%i==0&&i!=sqrt(num))
cout<<num/i<<" ";
}
return 0;
}

[shroudyboi]

to add elements in sorted order just use a set in c++ which add elements in o(logn) time

[davithov]

You showed on one concrete example that if a < b then a < sqrt(n) and b > sqrt(n). How to prove that in all cases? I mean that when we do some statement, we should show the correctness of the statement in all cases. I guess we can show it like this: if a < b and a < sqrt(n) lets assume that b < sqrt(n), but in that case we would have a * b < n => our assumption was wrong. Am I right? Yeh, sometimes very obvious things are not obvious for me :D.

[jlecampana]

Thank you for your advice, sir. I guess it's settled that there's no other way but the long path to becoming a good coder. :)
Incidentally, now that you mention TopCoder, two things: When it's the best time to get started with TopCoder Arena problems? (because it seems you have to have sharper skills for the type of problems seen there..); On the other hand; it'd be amazing If you could make a tutorial on TopCoder Competitions (although I know it'd be a lil' bit off your channel theme)

[jlecampana]

Fantastic! that's pretty much my motto... However, and even though I totally agree with you, There's the MOST RELEVANT Question I must Ask you:
Is it possible to recognize which pattern you must use to solve an algorithm immediately? ; Like... eventually, you see a problem, and you can say: "Hey! Divide and Conquer works for this one", etc.

[niraj]

I think the the condition in inner if incorrect. It should be i != A/i. The condition i != sqroot(n) will be incorrect for certain cases when we don't have perfect square root.

[duongnphong]

*How can I add all the value that I have found after the "for loop" into array A and value of b/i into array B?*
#include<stdio.h>
#include<math.h>
int main() {
int a=100, b=168, i, j;
int A[20] = { 0 }, B[20] = { 0 };

for (i = 1; i < sqrt(b); i++){
if (b % i == 0)
printf("%d, %d ", i, b / i);
}
return 0;
}

[Abhishekchandel]

for n=38808 this algorithm is skipping 198 cz of "if( i != sqrt(n) )" statement it should be replaced by "if( i != (A/i) )"

[jlecampana]

Really cool lesson, however, it always worries me when I notice you use a mathematical property to improve efficiency of an algorithm; I would have solved this problem using your first approach, because I lack the mathematical background to figure out behavior like this. I believe another example that builds upon this one is the GCD, right? - Which would be very complex if it wasn't for the Euclidean/Recursive implementation. - Will I ever gather all the Math needed to solve complex algorithms?

[kubrackian]

very good explanation of factorization algorithm, thanks

[steelpanther]

if the input to the algorithm is number 2, does the algorithm give correct output [1, 2] as factors?
The problem is that squareRoot2 is float type in C++, and I get wrong answers for factors when running loop up-to-including ceil(SquareRootN)

[jishudohare]

when we are placing i<=sqrt(n) if the outer for-loop, shouldn't the complexity be O(sqrt(n) * log(log(n))) ?

[thesnare]

Is there any calculator function you can use that will do this for you? I don't think I'd be being lazy, I mean I could also add 3 digit numbers by hand as well, but I was allowed to use a calculator to do so.

[HashDLS]

This was definitely a nice method but you can further optimize the running time of the program in another way.
Well this is just a suggestion but I think if you add a method to check if its a prime number then you can straight away print 1 and the number itself.So you don't need to get into the loop for prime numbers.
Yes definitely checking a number for being prime or not may take some time but I guess with some efforts the program would be more efficient.
Well this is just what I think :)

[subhamsingh]

This program is not working for n=48... please explain this

[priyanshu]

if n is perfect square then it work properly otherwise it skip the factors