# No of primes less than a given number

by srijithju
Tags: number, primes
 P: 994 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/...+problems%2527
P: 57
Thanks a lot for the reply ...

 Quote by Dragonfall 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.
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 .

P: 994
No of primes less than a given number

 Quote by srijithju 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.
Do you mean compute a prime < N, compute all primes < N, or the number of primes < N?

 Quote by srijithju 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.
"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.
HW Helper
P: 3,682
 Quote by Dragonfall I don't know how hard finding the number of primes less than N is.
The best known algorithm is exponential -- time ~ n^(1/2 + eps). I don't think there's any hope for finding a polynomial algorithm.
P: 994
 Quote by CRGreathouse The best known algorithm is exponential -- time ~ n^(1/2 + eps). I don't think there's any hope for finding a polynomial algorithm.
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.

 Related Discussions Fun, Photos & Games 0 General Math 6 Calculus & Beyond Homework 3 Calculus & Beyond Homework 1 Linear & Abstract Algebra 6