Simple C based approach on Sieve of Eratosthenes (by yours truly):
* https://github.com/intc/c-notes/blob/master/threads/4-thrd_e...
My favorite prime number generator
71–80 of 88 posts
Re: My favorite prime number generator
#72Earlier quoted context omitted.
That doesn't seem like a good way to generate "random" numbers, since it will only produce numbers with exactly two prime factors.
Correct. It will almost never produce an even number, so there's already one bit of entropy lost. It will also never produce lots of other numbers.
Thanks all, I hadn’t considered that but we do only use it for silly things and nothing work related but it’s worth a consideration.
Re: My favorite prime number generator
#73My 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!
It is still flash. Appears they incorporated aflax, a "run most of flash in js" library. https://github.com/aptana/aflax
Re: My favorite prime number generator
#74He said he has "used this code many times"... have you ever needed to find prime numbers in your daily programming?
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...
Re: My favorite prime number generator
#75Earlier quoted context omitted.
The list you need to process is large enough that it would be prohibitive to put it all in memory at once. Furthermore you do not start knowing things like how many primes to look at. Therefore generating and dealing with them iteratively makes for simple code and a lot fewer headaches.
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 Re: My favorite prime number generator
#76Earlier quoted context omitted.
The list you need to process is large enough that it would be prohibitive to put it all in memory at once. Furthermore you do not start knowing things like how many primes to look at. Therefore generating and dealing with them iteratively makes for simple code and a lot fewer headaches.
Why wouldn't someone just make a C++ class that keeps some state and call a method that gives them as many primes as they want, but runs 100x faster than python? Why would python yield somehow be better than this?
Project Euler is always about finding the right algorithm, and not raw performance.
With the right algorithm you can solve it in Python in a max of 30 seconds. With the wrong one, you sometimes can't solve it in C++ in the lifetime of the universe.
Therefore you should program in the language that you find it easiest to express yourself in. And not in a language chosen for raw speed.
Re: My favorite prime number generator
#77Earlier quoted context omitted.
Why wouldn't someone just make a C++ class that keeps some state and call a method that gives them as many primes as they want, but runs 100x faster than python? Why would python yield somehow be better than this?
Project Euler is always about finding the right algorithm, and not raw performance. With the right algorithm you can solve it in Python in a max of 30 seconds. With the wrong one, you sometimes can't solve it in C++ in the lifetime of the universe. Therefore you should program in the language that you find it easiest to express yourself in. And not in a language chosen for raw speed.
This is what you said before:
You'll see the win pretty quickly when you have to search a large range for primes.
This isn't just shifting the goal posts, you are now talking about something completely different.
With the right algorithm you can solve it in Python in a max of 30 seconds
Then you can do the same thing in C++, but when it runs the C++ program will be done 100x faster. A lot of modern C++ is as clean as python if you were being more explicit about types.
With the wrong one, you sometimes can't solve it in C++ in the lifetime of the universe.
Nothing about this makes any sense.
Therefore you should program in the language that you find it easiest to express yourself in. And not in a language chosen for raw speed.
If you continue on with python and need more speed you will run around in circles trying to get it while the C++ version is already done. Anything where speed can be a bottleneck is not fit to be written in pure python.
This pattern plays out over and over again. If something is resource intensive, a scripting language is not a long term solution.
Re: My favorite prime number generator
#78Earlier quoted context omitted.
Project Euler is always about finding the right algorithm, and not raw performance. With the right algorithm you can solve it in Python in a max of 30 seconds. With the wrong one, you sometimes can't solve it in C++ in the lifetime of the universe. Therefore you should program in the language that you find it easiest to express yourself in. And not in a language chosen for raw speed.
This is what you said before: You'll see the win pretty quickly when you have to search a large range for primes. This isn't just shifting the goal posts, you are now talking about something completely different. With the right algorithm you can solve it in Python in a max of 30 seconds Then you can do the same thing in C++, but when it runs the C++ program will be done 100x faster. A lot of modern C++ is as clean as…
Are you actually familiar with Project Euler?
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++ is a good choice for serious mathematical computing. But not always the best. https://www.hpcwire.com/2020/01/14/julia-programmings-dramat... shows the growing popularity of Julia, even for the most demanding computations.
Looking to the future, I would choose Rust over C++ for most new projects where people currently use 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.
So, yeah. C++ is great for what it's great for. But if I'm going some exploratory back of the envelope calculations, I'm still reaching for Python. And yield is one of the reasons why.
Re: My favorite prime number generator
#79He said he has "used this code many times"... have you ever needed to find prime numbers in your daily programming?
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.
Re: My favorite prime number generator
#80Earlier quoted context omitted.
This is what you said before: You'll see the win pretty quickly when you have to search a large range for primes. This isn't just shifting the goal posts, you are now talking about something completely different. With the right algorithm you can solve it in Python in a max of 30 seconds Then you can do the same thing in C++, but when it runs the C++ program will be done 100x faster. A lot of modern C++ is as clean as…
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 modern C++. Are you you sure you are up to date with modern C++? Most programs don't look too different than python due to for iteration and auto type deduction.