How to calculate how many primes there are of $N$ bits

996 Views Asked by At

Is there a way to calculate how many primes are exactly $N$ bits in length, without generating them? I know that you can calculate how many primes are below $N$, but not how/if you can calculate primes that are exactly $N$ bits.

1

There are 1 best solutions below

4
On BEST ANSWER

The smallest number with $N$ bits is $2^{N+1}$ The largest number with $N$ bits is $2^{N+2}-1$. If you find the number of primes below $2^{N+2}$ and subtract the number of primes below $2^{N+1}$ you have the number with exactly $N$ bits.