Prime Number Detection: Running Time of Algorithm

In summary, the algorithm for finding prime numbers has a running time of O(sqrt(N)) according to the internet. This is a polynomial time complexity and is not NP-complete or NP-hard. The specific algorithm being referred to is not mentioned, but it is stated that the complexity can vary based on the input size. However, for some algorithms like knapsack, the running time changes to pseudo-polynomial when the input size is large, but this is not the case for prime number and sorting algorithms.
  • #1
zak100
462
11
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.
 
Technology news on Phys.org
  • #2
zak100 said:
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
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
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. What is a prime number?

A prime number is a positive integer that is only divisible by 1 and itself. This means that it has exactly two factors.

2. Why is prime number detection important?

Prime numbers are important in many areas of mathematics, such as cryptography and number theory. They also have practical applications in computer science, such as in generating random numbers.

3. How do you detect prime numbers?

There are several algorithms for detecting prime numbers, such as the Sieve of Eratosthenes and the AKS primality test. These algorithms use different approaches, but all rely on the fact that prime numbers have only two factors.

4. What is the running time of a prime number detection algorithm?

The running time of a prime number detection algorithm depends on the specific algorithm used and the size of the number being checked. Some algorithms have a running time of O(log n), while others have a running time of O(n2).

5. Can we improve the running time of prime number detection algorithms?

Yes, there is ongoing research to develop more efficient prime number detection algorithms. For example, the AKS primality test has a running time of O(log6 n), which is currently the best known for deterministic algorithms.

Similar threads

  • Programming and Computer Science
Replies
9
Views
364
  • Programming and Computer Science
Replies
14
Views
2K
  • Programming and Computer Science
Replies
1
Views
951
Replies
9
Views
1K
  • Programming and Computer Science
Replies
2
Views
777
  • Programming and Computer Science
Replies
4
Views
899
  • Programming and Computer Science
Replies
8
Views
1K
  • Programming and Computer Science
Replies
30
Views
4K
  • Programming and Computer Science
Replies
3
Views
1K
Replies
5
Views
415
Back
Top