Prime Number Detection: Running Time of Algorithm

  • Thread starter zak100
  • Start date
  • #1
zak100
Gold Member
462
11

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.
 

Answers and Replies

  • #2
PeterDonis
Mentor
Insights Author
2019 Award
29,591
8,882
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.)
 
  • Like
Likes sysprog
  • #3
1,442
760
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:
  • Like
Likes Klystron
  • #4
zak100
Gold Member
462
11
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.
 
  • #5
1,442
760
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
 

Related Threads on Prime Number Detection: Running Time of Algorithm

  • Last Post
Replies
7
Views
2K
  • Last Post
Replies
6
Views
1K
Replies
6
Views
693
  • Last Post
Replies
4
Views
4K
  • Last Post
Replies
6
Views
2K
  • Last Post
Replies
11
Views
2K
  • Last Post
Replies
16
Views
10K
  • Last Post
Replies
17
Views
3K
Replies
7
Views
889
Replies
8
Views
4K
Top