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

Is This Prime?

isthisprime.com

Post reply on HN
Print view View original

131–139 of 139 posts

Re: Is This Prime?

#131

Post by maximus-decimus »

lalaithion wrote: post #17

This reminds me of my favorite in-person magic trick to do. First, memorize all the two-digit primes. 25 numbers isn't that hard to memorize. Then, tell someone "Oh, I can instantly tell whether a number is prime or not. Give me a number, I'll tell you whether it's prime." If they tell you a number between 1 and 100, use your memorized list. Otherwise, it's a game of cold reading; if they just generated a random stri…

That's a lot of effort just for tricking people into thinking you can tell if a number is prime.

Re: Is This Prime?

#132

Post by W0lf »

I am not doing _that_ type of number crunching in my daily work, so the following check (in Python) has probably lots of potential for improvement:

    def is_prime(n):
        return not True in [n%x == 0 for x in range(2, n/2)]

Re: Is This Prime?

#133

Post by PirateAvogadro »

W0lf wrote: post #132

I am not doing _that_ type of number crunching in my daily work, so the following check (in Python) has probably lots of potential for improvement: def is_prime(n): return not True in [n%x == 0 for x in range(2, n/2)]

You don't need to test up to n/2, just floor(sqrt(n)) will do

even better you only need to test the primes <= floor(sqrt(n))

Re: Is This Prime?

#135

Post by I_complete_me »

CamperBob2 wrote: post #114
Tempest1981 wrote: post #93

Earlier quoted context omitted.

We memorized pi to 7 decimal places... a few memorized it to 20+

Now I, even I, would celebrate In rhymes unapt, the great Immortal Syracusan, rivalled (sic) nevermore Who, in his wondrous lore, Passed on before, Left men his guidance How to circles mensurate.

Indeed. But I find "How I want a drink, alcoholic of course, after the heavy lectures involving quantum mechanics." sufficient for most of my needs.

Re: Is This Prime?

#136

Post by nilstycho »

Tempest1981 wrote: post #97
bbx wrote: post #37

Earlier quoted context omitted.

I agree. And I would add 51 to that.

They have stats on the most common mistakes here: https://isthisprime.com/game/record.php (loads very slowly) 51 is #1, then 57, then 1

It’s very surprising to me that 91 isn’t in the top 20. It’s beaten by 77 and 21?

Re: Is This Prime?

#137

Post by not2b »

nonfamous wrote: post #53
shric wrote: post #49

Earlier quoted context omitted.

No, at the cryptographic scale of prime numbers the lookup table would need to be far too big in terms of both time to generate and storage required. For smaller numbers see various prime sieves (Atkin, Eratosthenes)

Time to generate I get, but you could always augment the table over time and fall back to standard methods otherwise (and store the result). Storage I have a harder time wrapping my head around. Aren’t primes quite sparse at cryptographic magnitudes? And are the primes used for (say) 256-bit encryption about the same magnitude, narrowing the dimension of storage required?

https://en.wikipedia.org/wiki/Prime_number_theorem

Re: Is This Prime?

#138

Post by not2b »

thomasahle wrote: post #56
nonfamous wrote: post #53

Earlier quoted context omitted.

Time to generate I get, but you could always augment the table over time and fall back to standard methods otherwise (and store the result). Storage I have a harder time wrapping my head around. Aren’t primes quite sparse at cryptographic magnitudes? And are the primes used for (say) 256-bit encryption about the same magnitude, narrowing the dimension of storage required?

The primes are quite dense. There are roughly n/log(n) primes below n. Meaning 1 in 256 numbers with 256 bits are prime. That's 2^(248) primes. For RSA one typically use 2048 or 4096 bit primes.

Natural logarithm (base e, not base 2, so one in 177.4 for 256 bit numbers), but that doesn't change your general point.
Post reply on HN