title: Quickly determine if a number is prime in Python for numbers < 1 billion
body: <p>My current algorithm to check the primality of numbers in python is way to slow for numbers between 10 million and 1 billion. I want it to be improved knowing that I will never get numbers bigger than 1 billion.</p>
  
  <p>The context is that I can't get an implementation that is quick enough for solving problem 60 of project Euler: I'm getting the answer to the problem in 75 seconds where I need it in 60 seconds. <a href="http://projecteuler.net/index.php?section=problems&amp;id=60" rel="noreferrer">http://projecteuler.net/index.php?section=problems&amp;id=60</a></p>
  
  <p>I have very few memory at my disposal so I can't store all the prime numbers below 1 billion.</p>
  
  <p>I'm currently using the standard trial division tuned with 6k±1. Is there anything better than this? Do I already need to get the Rabin-Miller method for numbers that are this large.</p>
  
  <pre><code>primes_under_100 = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
  def isprime(n):
      if n &lt;= 100:
          return n in primes_under_100
      if n % 2 == 0 or n % 3 == 0:
          return False
  
      for f in range(5, int(n ** .5), 6):
          if n % f == 0 or n % (f + 2) == 0:
              return False
      return True
  </code></pre>
  
  <p>How can I improve this algorithm?</p>
  
  <p>Precision: I'm new to python and would like to work with python 3+ only.</p>
  
  <hr>
  
  <p><strong>Final code</strong></p>
  
  <p>For those who are interested, using MAK's ideas, I generated the following code which is about 1/3 quicker, allowing me to get the result of the euler problem in less than 60 seconds!</p>
  
  <pre><code>from bisect import bisect_left
  # sqrt(1000000000) = 31622
  __primes = sieve(31622)
  def is_prime(n):
      # if prime is already in the list, just pick it
      if n &lt;= 31622:
          i = bisect_left(__primes, n)
          return i != len(__primes) and __primes[i] == n
      # Divide by each known prime
      limit = int(n ** .5)
      for p in __primes:
          if p &gt; limit: return True
          if n % p == 0: return False
      # fall back on trial division if n &gt; 1 billion
      for f in range(31627, limit, 6): # 31627 is the next prime
          if n % f == 0 or n % (f + 4) == 0:
              return False
      return True
  </code></pre>