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 | Science Articles, Homework Help, Discussion**

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!

# Trial division Primality

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