Friday, January 30, 2015

386: Finding Primes the Euler Way

Trying to find a prime number seems difficult. You have to test it against divisibility by all of the primes that are smaller. But what if there were a formula?
Take a counting number, multiply it by itself, subtract it from the result and then add 41

1x1 = 1; 1-1 = 0; 0+41 = 41. That's prime.
2x2 = 4; 4-2 = 2; 2+41 = 43. That's prime.
3*3 = 9; 9-3 = 6; 6+41 = 47. That's prime, too.
4*4=16; 16-4=12; 12+41= 53. That's also prime.

How good is this idea?
Will it ever fail?

1 comment:

  1. We were recently playing around with 23 in different bases, checking when it is prime. Pretty easy to see it won't be for bases that are multiples of 3. However, it works for 4, 5, 7, so looks pretty good . . . Also for 1 and 2 if you want to just interpret as 2*base+3.

    ReplyDelete