The efficiency of prime factoring algorithms

Question

I'm trying to understand what the issue is with creating an efficient prime factorisation algorithm. Specifically, the research I've done so far says that no algorithm has yet been discovered which can find the prime factors of a number in O(n²) time. However, the obvious algorithm to me is something like (pseudocode)

method(int number, ArrayList<int> listOfPrimes)
{
    int x = 0;
    for (int i : listOfPrimes)
     {
      for (int j : listOfPrimes)
       { 
         if (i * j = number)
          {
            x = i*j;
          }
        }
      }
     return x;
 }

I think method is O(n²), where n is the size of the list. Clearly my understanding of this issue is flawed or there wouldn't be such a fuss about prime factorisation. Where am I going wrong?

Answer 1

A more optimal way would be

method(int number, ArrayList<int> listOfPrimes)
{
    int x = 0;
    for (int i : listOfPrimes)
    {
        while(number%i == 0){
            number /= i;
            x++;
        }

    }
    return x;
 }

this returns the count prime factors of a number. the complexity would be

O(n + number_of_prime_factors)

where n is the length of listOfPrimes

Answer 2

As alluded to by @dmuir, your "n" is not the correct "n". Otherwise a trivial O(n) algorithm to factor would be:

factor(n){
   for (int i=2; i<n; i++) {
      if (n % i == 0) {
         print("found factor:", i);
         return i;
      }
   }
}

For factoring, the size of the input is measured in digits, so "n" is the number of digits or bits in the number. The best algorithms have a very complicated complexity that requires some number theory to understand, but is "greater than" polynomial time yet "less than" exponential time, where the quoted phrases can be made formal. For this reason the complexity is sometimes referred to as "subexponential".