ok so I thought of this factoring algorithm, and I did some quick analysis on it (attached picture, time is in seconds * 5). It appears to be polynomial. However, when I see the basic brute force factoring algorithm I think thats also polynomial. So before I get excited over nothing. Can someone explain to me why the brute force factoring algorithm shown below is exponential time? What I get is approximately O(n^m) where n is the number and m is the number of factors.(adsbygoogle = window.adsbygoogle || []).push({});

basically it searches till it finds a factor, and then it returns a list of the concatination of the factors of the two factors it found (i and n/i). For prime numbers it just returns the number. The main loop is obviously O(n). And as far as I can tell the function is recursively called on the order of m where m is the number of factors. This gives O(n^m).Code (Text):brute-force(n)

{

for(i = 2; i < n/2; i++)

{

if(n%i == 0)

return CONCAT(brute_force(i), brute_force(n/i));

}

return n;

}

**Physics Forums | Science Articles, Homework Help, Discussion**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Factoring algorithm time

**Physics Forums | Science Articles, Homework Help, Discussion**