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 - The Fusion of Science and Community**

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

Loading...

Similar Threads - Factoring algorithm | Date |
---|---|

I Question about the Divisor Function/Sums and Project Euler | Feb 16, 2018 |

I Why is Graham's number a factor of 3? | Jan 11, 2018 |

B How can I calculate this hyperbola's equation? | Nov 19, 2017 |

B Non-algorithmic math | Oct 13, 2017 |

B What are the different methods of factoring polynomials? | Jul 1, 2017 |

**Physics Forums - The Fusion of Science and Community**