# Prime Number Detection: Running Time of Algorithm

zak100
TL;DR Summary
From the internet, I found that the running time of algorithm to find prime number is O(sqrt(N)).
I have 3 questions: Can we say that the running time is O(log^2N) for detection of Prime number? For large values of N, can we say that its a pseudo-polynomial algorithm? Is this true for Sorting algorithms also?

Zulfi.
Hi,

I want to know if the algorithm to find prime number has running time O(sqrt(N)) or O(log^2N). log^2N is better than sqrt(N). Also for large values can it become a pseudo polynomial algorithm?

Zulfi.

Mentor
From the internet, I found that the running time of algorithm to find prime number is O(sqrt(N)).

First, you need to give a specific reference; "from the internet" is not enough.

Second, there are multiple different possible algorithms for finding prime numbers; you need to say which one you are talking about. (Giving a reference will naturally help with that.)

• sysprog
sysprog
The running time of primality testing is polynomial with respect to the size of the input -- it's not NP-complete or (worse-yet) NP-hard -- detecting whether a number is prime can be done in polynomial time -- https://en.wikipedia.org/wiki/Primality_test

Last edited:
• Klystron
zak100
Hi,

https://softwareengineering.stackex...f-the-algorithm-to-check-if-a-number-is-prime
In terms of magnitude of Number it is O(sqrt(N)) and also the worst case:but average case is O(sqrt(N))/log N.