Prime Number Detection: Running Time of Algorithm

[zak100]

TL;DR

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.

 

[PeterDonis]

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

 

[zak100]

Hi,

Thanks for your response.
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.

What is your answer?

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 -

-
For some algorithms like knapsack, the running time changes from polynomial to pseudopolynomial when the input size is large, why is this different for prime number and sorting algorithms?

Zulfi.

 

[sysprog]

Time complexity of the sieve of Eratosthenes is O(n log log n); for more generality (inclusive of some specificity and references), you could look at: https://en.wikipedia.org/wiki/Sieve_theory