An algorithm to find factors or primes in linear time - I was wrong!!

 Edited: I was wrong in this case on as how to find the time complexity of an algorithm. At another forum I got a more correct evaluation, for reading the answer yourself please check this link: http://stackoverflow.com/questions/5581040/i-have-a-new-algorithm-to-find-factors-or-primes-in-linear-time-need-verificati

This algorithm doesn’t find factors or decides if a given number is prime in linear time. Apologies for the mistake. End Edited
Prime Numbers had fascinated me for some time. Particularly when I studied in my school and college, I came across them as numbers which had just two factors, 1 and itself. While in college (around 2003), I came to know of the interesting find that even computers found it hard to find if a given number is prime or not. And our simple practice C and Java programs usually had a prime number finding program apart from the usual “Hello World”.
As our studies got advanced I came across algorithm analysis and knew that basic prime finding algorithms are in fact exponential in time.This kept me thinking, in this world where we say nothing is impossible.. can one not find an algorithm or way to find if a given number is prime or not faster.
Hmm.. after working around with circles if they could give an answer, finally I was able to find a way to find factors of a given number (hence primes too) in linear time.
Below is the skeleton of the algorithm, that I realized:
 Input: A Number (whose factors is to be found)
 Output: The two factors of the Number. If the one of the factor found is 1 then it can be concluded that the number is prime.


 Declare integers N, mL, mR, r, temp1;
 mR = mL = square root of (N); //square root is rounded to integer if required.
 /*Check if perfect square*/
 if mL*mR equals N then
 {
   r = 0; //answer is found
   End;
 }
 mR = N/mL;
 r = N%mL;
 while mL not equals r do
 {
   while mL is greater than r do
   {
      mL = mL-1;
      r = r+ mR;
   }
   while mL is smaller than r do
   {
      r = r - mL;
      mR = mR+1;
   }
 }
 mR = mR + 1;
 r = 0;
 End; //mR and mL has answer
Above the algorithm is given in its simplest form, in which I realized it. This algorithm takes about 5*N (where N is the given number) time to find if a given number is prime or not. Also we can definitely make it faster, by observing patterns and devising newer ones based on the one above; as I had done after several test runs.


Don’t hesitate to contact me if you need to know more about this or want to know about the faster version.