Greetings,(adsbygoogle = window.adsbygoogle || []).push({});

This is very simple, and obviously i'm missing something trivial, but I still don't get it.

An algorithm is said to run in polynomial time if it runs in O(n^K) time.

That's why dijkstra for example, who runs in O(V^2), runs in polynomial time.

That said, my doubt is the following:

If a brute-force trial division primality check algorithm, runs in O(n^(1/2)), why it isn't considered in polynomial time?

Thanks beforehands,

Mourinho

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

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

# Trial division Primality

Loading...

Similar Threads - Trial division Primality | Date |
---|---|

B Divisibility by p^p | Jan 25, 2018 |

E to the -y plus trial and error math? | Feb 18, 2014 |

Probability of an event occurring at least once over n trials | Mar 18, 2013 |

Trial and Error | Jan 22, 2011 |

Sudoku scanning and trial and error | Oct 23, 2005 |

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