# Prime Number Detection: Running Time of Algorithm

Gold Member

## 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.

## Main Question or Discussion Point

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.

Related Programming and Computer Science News on Phys.org
PeterDonis
Mentor
2019 Award
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
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
Gold Member
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.