Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

My favorite prime number generator

eli.thegreenplace.net

Post reply on HN
Print view View original

81–88 of 88 posts

Re: My favorite prime number generator

#81

Post by svat »

SeanLuke wrote: post #59

Believe it or not, there exists a closed-form equation which computes the nth prime number. It's Willans's formula: p_n = 1 + Sum_{i=1}^{2^n} Floor((n/(Sum_{j=1}^{i} Floor((Cos((j-1)!+1)/j) Pi)^2)))^(1/n)) https://en.wikipedia.org/wiki/Formula_for_primes https://www.youtube.com/watch?v=j5s0h42GfvM It's not fast but it really does work.

That video is actually great!

The last time this formula came up, I added some references to the Wikipedia article (current version: https://en.wikipedia.org/w/index.php?title=Formula_for_prime... about the "worthlessness" of such formulas, but it doesn't deter people from being interested in that formula… as long as they don't imagine it's useful in any way, it's fine to enjoy its perverse cleverness, I suppose.

The video does well to quote Wilf on “the disease was preferable to the cure” and to end with “Could it [C. P. Willans] be a pseudonym for someone who didn't want to tarnish their reputation by writing about useless prime-generating formulas?” :-) Dudley (who mentions a large list of other such formulas) also has a nice conclusion:

> The conclusion to be drawn from all this, I think, is that formulas for formulas' sake do not advance the mathematical enterprise. Formulas should be useful. If not, they should be astounding, elegant, enlightening, simple, or have some other redeeming value.

Re: My favorite prime number generator

#82

Post by btilly »

CyberDildonics wrote: post #80
btilly wrote: post #78

Earlier quoted context omitted.

Are you actually familiar with Project Euler? https://projecteuler.net/ Absolutely none of your arguments make sense in a context of a series of programming puzzles of fixed size. Back in the real world, there is a real need for exploratory programming on mathematical problems. I' prefer to use Python for that. If your problems are statistical, R is a better choice. C++ is a poor fit for exploratory programming. C++…

C++ is a poor fit for exploratory programming. It works fine for me. Are you sure this isn't just because you don't have a lot of practice with C++? It seems bizarre to me that C++ evangelists can talk about type safety and ignore memory safety, when memory safety is a giant problem for security and correctness in any large program. This has nothing to do with the current thread, but this isn't really a problem in mo…

sigh

I have no idea why you are trying to evangelize C++ here. I use a wide variety of languages for different purposes. For Project Euler type tasks I switched to Python about 15 years ago because of yield, and the convenience of using objects as hash keys. If you make different choices and they work for you, then have fun.

Re: My favorite prime number generator

#83

Post by kmill »

btilly wrote: post #75
kmill wrote: post #65

Earlier quoted context omitted.

The generator is already maintaining a dictionary containing multiple lists that hold all the primes found so far. Even if it instead kept yielding a list of all the primes so far (rather than the most recent prime) it would take less than twice the memory usage. I'd say the flexibility to not need to know how big of a prime you'll need is the main draw.

I obviously have a version without the memory issue. The programming flexibility is indeed the win. def primes (): yield 2 yield 3 f = {} n = 5 for p in primes(): if p == 2: continue p2 = p*p while n

This allocates a dictionary and the primes() generator for every single prime generated though, so it still has the memory issue, unless there's something I'm missing about how it works?

Re: My favorite prime number generator

#84

Post by CyberDildonics »

btilly wrote: post #82
CyberDildonics wrote: post #80

Earlier quoted context omitted.

C++ is a poor fit for exploratory programming. It works fine for me. Are you sure this isn't just because you don't have a lot of practice with C++? It seems bizarre to me that C++ evangelists can talk about type safety and ignore memory safety, when memory safety is a giant problem for security and correctness in any large program. This has nothing to do with the current thread, but this isn't really a problem in mo…

sigh I have no idea why you are trying to evangelize C++ here. I use a wide variety of languages for different purposes. For Project Euler type tasks I switched to Python about 15 years ago because of yield, and the convenience of using objects as hash keys. If you make different choices and they work for you, then have fun.

double sigh

You seem to be saying there is some advantage to python because of the yield feature and I just don't think that's true. You can keep state in a class and call a method. There are a lot of disadvantages though.

triple sigh

Re: My favorite prime number generator

#85

Post by jacknews »

Nice, I like the optimization replacing the list, and just hunting for the next 'free' composite for the prime.

Teaching my kids coding, we also arrived at most of the other optimizations, in Janet:

  (defn primes-sieve []
    (fiber/new (fn []
      (yield 2) # the only even prime, yield it explicitly.
  
      (let [sieve (table/new (math/pow 2 12))]
        (loop [n :range [3 nil 2]]  # only odd numbers
          (if-let [current-composite (sieve n)]
            (do 
              (each prime-factor current-composite
                (let [next-composite-key (+ n (* 2 prime-factor))] # add 2*prime-factor, else composite would be even
                  (if-let [next-composite (sieve next-composite-key)]
                    (array/push next-composite prime-factor)
                    (put sieve next-composite-key @[prime-factor]))))
              (put sieve n nil))
            (do
              (yield n)
              (put sieve (* n n) @[n])) # next composite is n^2. Anything less is composite a smaller prime, already in the sieve
            ))))))

Re: My favorite prime number generator

#86

Post by btilly »

kmill wrote: post #83
btilly wrote: post #75

Earlier quoted context omitted.

I obviously have a version without the memory issue. The programming flexibility is indeed the win. def primes (): yield 2 yield 3 f = {} n = 5 for p in primes(): if p == 2: continue p2 = p*p while n

This allocates a dictionary and the primes() generator for every single prime generated though, so it still has the memory issue, unless there's something I'm missing about how it works?

Put a debugging statement in and you'll verify that the dictionary only contains primes up to the square root of the one just generated.

To do that it recursively contains a second prime generator that only produces up to the square root. Which contains one that produces up to the fourth root. And so on until you get down to 3. The work and memory for those recursive generators is a rounding error compared to the initial prime generator. The work and memory saved by not keeping unnecessary primes is a significant win.

Re: My favorite prime number generator

#87

Post by thrownblown »

Exuma wrote: post #79
thrownblown wrote: post #74

Earlier quoted context omitted.

to those who flagged my "do you even crypto bro?" comment: even a little research into cryptography will inform you that prime numbers are used heavily in encryption algorithms. https://stackoverflow.com/questions/439870/why-are-primes-im...

Don't try to pull a "even a little research" bullshit comment on me. "even a little research" will tell you people shouldn't roll your own cryptography and to just use a library. So, this still doesn't answer my question.

you'll never be in cicada 3301 with that kinda attitude my guy!

but to counter your point: people do have to write those libraries that you depend on. others have to validate them, and yet still others are doing their best efforts to invalidate them and attack them.

but you are correct that most people should not roll their own cryptography suites.

Re: My favorite prime number generator

#88

Post by kmill »

btilly wrote: post #86
kmill wrote: post #83

Earlier quoted context omitted.

This allocates a dictionary and the primes() generator for every single prime generated though, so it still has the memory issue, unless there's something I'm missing about how it works?

Put a debugging statement in and you'll verify that the dictionary only contains primes up to the square root of the one just generated. To do that it recursively contains a second prime generator that only produces up to the square root. Which contains one that produces up to the fourth root. And so on until you get down to 3. The work and memory for those recursive generators is a rounding error compared to the ini…

Oh, thanks for the explanation, I get how it works now. I hadn't seen this trick for an unbounded prime sieve before, and it's a nice idea.
Post reply on HN