5 ms·

Up to a number x, there are approximately a = x/(log_2(x)) prime numbers. To a first approximation, we can assume that each of these numbers has b = log_2(x) bi

Up to a number x, there are approximately a = x/(log_2(x)) prime numbers. To a first approximation, we can assume that each of these numbers has b = log_2(x) bits. So to store all the prime numbers from 1 to x you need about a*b bits, or just 'x'. So to implement this approach you would need to store and search a space that grows linearly with the size of the largest number you expect to encounter. However, this is unnecessary because we have faster ways of telling a number is prime other than storing all the prime numbers up to that point.

xyzzyz 9y ago
Why log_2? It should be natural logarithm.
- bonzini 9y ago
  It only differs by a constant factor, so in the end it doesn't matter when you want the asymptotic complexity of storing all primes up to x.
  - xyzzyz 9y ago
    Sure, you would still get that the space needed grows linearly, but you're off by almost 50% in your storage requirements. More importantly, you're confusing people with explicitly wrong statement for no benefit, people who might not realize that it's actualy ln, not log_2, and spread the mistake to other people.
    - jacobolus 9y ago
      The bound we have is apparently: https://en.wikipedia.org/wiki/Prime-counting_function#Inequalities https://en.wikipedia.org/wiki/Prime-counting_function#Inequa... x/log x < π(x) < 1.25506x/log x If you want to rewrite that using log2, you get: 1.44270x/log2 x < π(x) < 1.81067x/log2 x I would hardly call the previous poster’s comment an “explicitly wrong statement for no benefit”. We’re talking about number of bits here.
      - xyzzyz 9y ago
        You're missing the point. Asymptotically, we have much better bound than 1.25506 -- the asymptotic bound is indeed 1+e for any e > 0, as the prime number theorem explicitly says that lim pi(n)/(n/log n)) = 1. The constant 1.25506... = 30 * log(113)/113 is only relevant because that's the the smallest global bound, which is there to take care of n = 113. If you rewrite it to log_2, you get the 1.442... constant, which throws your calculations off by "almost 50%" I mentioned in my comment above. And yeah, it doesn't change anything in the qualititative analysis of storage needs, but that's not my point -- my point is that in math, you should avoid saying things that are explicitly wrong, unless there are very good reasons to do so.
- wickawic 9y ago
  You're totally right, I was stuck in CS world and write log_2 instead of ln absent mindedly
deleted 9y ago
[deleted]

xyzzyz 9y ago

Why log_2? It should be natural logarithm.

bonzini 9y ago
It only differs by a constant factor, so in the end it doesn't matter when you want the asymptotic complexity of storing all primes up to x.
- xyzzyz 9y ago
  Sure, you would still get that the space needed grows linearly, but you're off by almost 50% in your storage requirements. More importantly, you're confusing people with explicitly wrong statement for no benefit, people who might not realize that it's actualy ln, not log_2, and spread the mistake to other people.
  - jacobolus 9y ago
    The bound we have is apparently: https://en.wikipedia.org/wiki/Prime-counting_function#Inequalities https://en.wikipedia.org/wiki/Prime-counting_function#Inequa... x/log x < π(x) < 1.25506x/log x If you want to rewrite that using log2, you get: 1.44270x/log2 x < π(x) < 1.81067x/log2 x I would hardly call the previous poster’s comment an “explicitly wrong statement for no benefit”. We’re talking about number of bits here.
    - xyzzyz 9y ago
      You're missing the point. Asymptotically, we have much better bound than 1.25506 -- the asymptotic bound is indeed 1+e for any e > 0, as the prime number theorem explicitly says that lim pi(n)/(n/log n)) = 1. The constant 1.25506... = 30 * log(113)/113 is only relevant because that's the the smallest global bound, which is there to take care of n = 113. If you rewrite it to log_2, you get the 1.442... constant, which throws your calculations off by "almost 50%" I mentioned in my comment above. And yeah, it doesn't change anything in the qualititative analysis of storage needs, but that's not my point -- my point is that in math, you should avoid saying things that are explicitly wrong, unless there are very good reasons to do so.
wickawic 9y ago
You're totally right, I was stuck in CS world and write log_2 instead of ln absent mindedly

deleted 9y ago

[deleted]