comment by user-inactivated

a thoughtful web.

Good ideas and conversation. No ads, no tracking. Login or Take a Tour!

user-inactivated · 3348 days ago · link · · parent · post: Long-Lost Nikola Tesla Drawings Reveal Map To Multiplication

Still, it is irrelevant, because as all mathematicians know, there is no known pattern or algorithm to compute prime numbers

Pedantry: there are lots of (cheap) algorithms to list prime numbers. Euclid gave a nice one in proving there were infinitely many primes.

    p = n = 1    while True:
        print p+1
        n += 1        p *= n

and there are (expensive) algorithms to list all of them (because you can test for primality, you can just walk through all the natural numbers and check each one). There just isn't a cheap algorithm to list all of them.

markup tips · 0

dingus · 3347 days ago · link ·

The seive of Erasthones is much faster than doing a 100% perfect primality test on every number.

+discuss+discuss

–

user-inactivated · 3347 days ago · link ·

This is true if you only want all the primes up to N, but if you want an infinite list of primes the sieve of Eratosthenes isn't going to give it to you. You could extend it, of course, but then you're just optimizing for time over space.