H. Chase Stevens Logo

Most Common Tags

  1. programming
  2. python
  3. code
  4. philosophy
  5. evolution
  6. game design
  7. probability
  8. video games
  9. genetic algorithms
  10. government

Archives

Loading

Fermat's Primality Test

posted on: Sunday, January 22, 2012 (4:03 pm) by

Recently, I was reading about some sample interview questions used (at some point) by Google. One such question was "what are the first 10 consecutive digits of e that form a prime number?" Curious, I went to Wikipedia and looked up some primality tests that I could run on 10-digit prime candidates (if you'll forgive the pun) from e. One such test was Fermat's Primality Test, which can be used to probabilistically assess a number's primality (it fails on Carmichael numbers, et alia). I've written up a short python script which runs the test on the numbers 1 to 100 using computed probable primes as possible coprimes and returns all probable primes.

Download

def test(end):
    candidates = range(1,end+1)
    primes = list()
    for candidate in candidates:
        prime = True
        for prime in primes:
            if candidate % prime:
                test_result = ((prime ** (candidate - 1)) % candidate)
                print "Candidate: %s, Prime: %s, Result:%s" %(candidate,prime,test_result)
                if test_result != 1:
                    prime = False
                    break
        if prime:
            primes.append(candidate)
    return primes

test(100)

Of course, the astute reader will notice that the above program exhaustively checks each candidate for primality for coprimality with all other probable primes, meaning that even simple trial division would be considerably faster. However, a quick modification to the program that only tested against a fixed number of random probable primes would lead to an increase in efficiency.

Tags: code, math, number theory, probability, programming, python