My favorite prime number generator • Hacker News Board

Re: My favorite prime number generator

#21

Post by philipLutz » Wed, Aug 23, 2023, 4:10 PM UTC

masklinn wrote: post #18

philipLutz wrote: post #14

I enjoyed this, but I am a little stuck on how stuck the author is on yield. If one ends up creating a large list of prime numbers with this generator, why not just return a large list of prime numbers? The author clearly notes how optimizing Python code is "odd" when you can more easily switch languages, but languages like C/C++/Rust would not have pretty code because it does not have yield. It is obvious that retur…

> If one ends up creating a large list of prime numbers with this generator But one does not always end up creating a large list of prime numbers, do they? > why not just return a large list of prime numbers? Because that requires upfront knowledge of the filtering factor or absence thereof. A generator means you don't care, you generate an infinite sequence and the consumer is free to do whatever they want. > It is…

"I can't try to rewrite it in C++ or Rust for now, due to the lack of generator support; the yield statement is what makes this code so nice and elegant, and alternative idioms are much less convenient."

Re: My favorite prime number generator

#22

Post by [deleted] » Wed, Aug 23, 2023, 4:14 PM UTC

proactivesvcs wrote: post #11

tantalor wrote: post #5

My favorite prime number generator is http://alpha61.com/primenumbershittingbear/

It doesn't need Flash Player any more? It's the year 2023 and I can run the Prime Number Shitting Bear again? Hallelujah!

[deleted]

Re: My favorite prime number generator

#23

Post by btilly » Wed, Aug 23, 2023, 4:16 PM UTC

philipLutz wrote: post #14

I enjoyed this, but I am a little stuck on how stuck the author is on yield. If one ends up creating a large list of prime numbers with this generator, why not just return a large list of prime numbers? The author clearly notes how optimizing Python code is "odd" when you can more easily switch languages, but languages like C/C++/Rust would not have pretty code because it does not have yield. It is obvious that retur…

Try solving some Project Euler problems. You'll see the win pretty quickly when you have to search a large range for primes.

Re: My favorite prime number generator

#24

Post by masklinn » Wed, Aug 23, 2023, 4:18 PM UTC

philipLutz wrote: post #21

masklinn wrote: post #18

Earlier quoted context omitted.

> If one ends up creating a large list of prime numbers with this generator But one does not always end up creating a large list of prime numbers, do they? > why not just return a large list of prime numbers? Because that requires upfront knowledge of the filtering factor or absence thereof. A generator means you don't care, you generate an infinite sequence and the consumer is free to do whatever they want. > It is…

"I can't try to rewrite it in C++ or Rust for now, due to the lack of generator support; the yield statement is what makes this code so nice and elegant, and alternative idioms are much less convenient."

That is the context of the first sentence in your comment, pretty much the only part I left alone.

Everything I replied to is the opinion you personally expressed.

And note that the author had already preempted your comment in the first place:

> When we want a list of all the primes below some known limit, gen_primes_upto is great, and performs fairly well. There are two issues with it, though:

> We have to know what the limit is ahead of time; this isn't always possible or convenient.

Re: My favorite prime number generator

#25

Post by CyberDildonics » Wed, Aug 23, 2023, 4:23 PM UTC

btilly wrote: post #23

philipLutz wrote: post #14

I enjoyed this, but I am a little stuck on how stuck the author is on yield. If one ends up creating a large list of prime numbers with this generator, why not just return a large list of prime numbers? The author clearly notes how optimizing Python code is "odd" when you can more easily switch languages, but languages like C/C++/Rust would not have pretty code because it does not have yield. It is obvious that retur…

Try solving some Project Euler problems. You'll see the win pretty quickly when you have to search a large range for primes.

Why would that be true?

Re: My favorite prime number generator

#26

Post by rullelito » Wed, Aug 23, 2023, 4:36 PM UTC

My favorite one:

    d = defaultdict(list)
    
    # Magic
    for i in range(2, 10000):
            for y in i in d and d.pop(i) or [i]:
                d[i+y] += (y,)
    
    # Not sure how to print this in a succinct way
    print(sorted(list(set().union(*d.values()))))

Re: My favorite prime number generator

#27

Post by anaphor » Wed, Aug 23, 2023, 4:46 PM UTC

There's a functional / lazy version I like that uses a priority queue in order to get the next prime number https://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf

It basically uses the priority queue to store all the composites up to a certain point and then you can assume the next one is prime.

I had some (admittedly not well written) code for it too https://gist.github.com/weskerfoot/4699275

It can also incorporates the wheel factorization optimization mentioned in this article.

Re: My favorite prime number generator

#28

Post by anonymoushn » Wed, Aug 23, 2023, 4:58 PM UTC

ChrisCinelli wrote: post #10

The Sieve of Atkin is VERY fast at generating primes between 1 and n. It asymptotically speeds up the process of generating prime numbers. It has time complexity O(n/(log log n)) https://www.baeldung.com/cs/prime-number-algorithms

Your link seems to say it has time complexity O(n)?

Re: My favorite prime number generator

#29

Post by oxxoxoxooo » Wed, Aug 23, 2023, 5:33 PM UTC

And another one:

The Genuine Sieve of Eratosthenes https://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf

Re: My favorite prime number generator

#30

Post by jonahx » Wed, Aug 23, 2023, 5:48 PM UTC

max_ wrote: post #6

In J generating prime numbers is simply p:21, that gives you 79 which is the 21st prime number. It is so fast, I wonder what the algorithm behind it is. [0]: https://code.jsoftware.com/wiki/Vocabulary/pco

> I wonder what the algorithm behind it is.

Noted in the details section of the link you provided:

"Primality testing on numbers larger than (2^31) uses the probabilistic Miller-Rabin algorithm."