1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

No of primes less than a given number

  1. Aug 25, 2009 #1
    After reading 1 of the posts in this forum , I had a look at the millenium problems .
    There I saw the problem of proving if N=NP .

    I really did not understand what is NP and what is P ( I checked the Wikipedia link but this got me even more confused ... It talked of a non deterministic Turing machine whatever that is )

    This is my doubt :
    There exists an algorithm (AKS algorithm) which is able to calculate if a number is prime in with polynomial complexity.

    Now if it is proved that N=NP , does that imply that you can also develop an algorithm to find all primes less than or equal to a prime in polynomial time ?

    Could someone suggest some literature where I can read about what NP / P complexity classes are. Also I am not sure of what exactly is the meaning of polynomial complexity also with respect to treatment of integers ( for eg. checking if N is prime)

    This is my understanding of complexity of an algo:
    Complexity refers to number of calculations to be done by a computer to reach the result ( find the solution) expressed as a function of the size of the input.

    Now to check if N is prime we would first have to express N as a binary number. Now in the process of checking if it is prime we may have to add / multiply / divide these numbers . What we be the complexities of these individual steps ..
    To add 2 numbers we get answer in 1 step ( 1 clock cycle of ALU of computer) if the size of number is within the CPU register width , but if it exceeds this width we need more cycles depending on how large the number is . Similarly for multiplication and division . So how do we calculate the actual complexity of a specific problem ???
    Please help
  2. jcsd
  3. Aug 25, 2009 #2
    You can think of NP as the class of problems whose solutions can be VERIFIED in polynomial time. ie, if I ask you to factor N, and you give me p and q, I can multiply them easily and check whether N=pq. While P is the class of problems whose solutions can be COMPUTED in polynomial-time, like sorting N numbers.

    Even if P=NP, there might not be a polynomial-time algorithm that will compute the number of primes less than N exactly. But I think this is due to our lack of understanding of the prime numbers rather than complexity. So this would be a problem in number theory, not computational complexity.

    Any textbook on "computational complexity" will do. But I suggest taking a course if you really want to learn about it.

    If you just want a superficial understanding of the millennium problems (it would take a lot of math to truly understand any of them), read http://www.chapters.indigo.ca/books...ch+Books:+%27devlin+the+millenium+problems%27
    Last edited: Aug 25, 2009
  4. Aug 26, 2009 #3
    Thanks a lot for the reply ...

    yes I can see that maybe the reason we cannot calculate all primes < N in polynomial time is probably due to our lack of understanding of number theory, but what I mean to as is if P=NP , then does not that mean that theoretically an algo exists that can compute primes < N in polynomial time , though we are unaware of such an algo.

    Now regarding the explanation you gave of a P problem and an NP problem -

    So if we consider the problem of finding all the prime numbers then that means :

    a) This problem is most certainly a NP problem because we already know of an algorithm that can verify a certain solution ( i.e. can check if a given number is prime) in polynomial time.
    b) But we are not sure if the problem is P .

    But considering this problem - is this not a counter example to showing P=NP , because we know there are infinitely many primes so how are we supposed to calculate an infinite number of solutions in polynomial time ? - or is it that all the prime numbers can be expressed by some formula ( which at present we do not know of) , and it is enough to find this formula in polynomial time .
  5. Aug 26, 2009 #4
    Do you mean compute a prime < N, compute all primes < N, or the number of primes < N?

    "Finding all the primes" less than N is certainly not an NP problem, because there's no way you can verify all the approx. N/log N many primes in polynomial time. This problem isn't even in PSPACE.

    However, finding a prime less than N is NP. In fact, it's most likely P. However since this problem isn't NP-hard, the existence of a polynomial-time algorithm for solving it does not mean P=NP.

    I don't know how hard finding the number of primes less than N is.
    Last edited: Aug 26, 2009
  6. Aug 26, 2009 #5


    User Avatar
    Science Advisor
    Homework Helper

    The best known algorithm is exponential -- time ~ n^(1/2 + eps). I don't think there's any hope for finding a polynomial algorithm.
  7. Aug 26, 2009 #6
    Do you mean (1/2+eps)^n?

    There might not be a polynomial algorithm to find the exact number, but it can be approximated very well -- the prime number theorem, for example -- by polynomial algorithms.

    I don't know where this problem sits in the hierarchy, either.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Similar Discussions: No of primes less than a given number
  1. Prime Number (Replies: 15)

  2. Prime numbers (Replies: 12)

  3. Prime numbers (Replies: 8)