Fastest way of testing if a number is prime?

Question

I'm trying to get a fast way to determine if a number is prime using Python.

I have two functions to do this. Both return either True or False.

Function isPrime1 is very fast to return False is a number is not a prime. For example with a big number. But it is slow in testing True for big prime numbers.

Function isPrime2 is faster in returning True for prime numbers. But if a number is big and it is not prime, it takes too long to return a value. First function works better with that.

How can I come up with a solution that could quickly return False for a big number that is not prime and would work fast with a big number that is prime?

def isPrime1(number): #Works well with big numbers that are not prime
    state = True
    if number <= 0:
        state = False
        return state
    else:          
        for i in range(2,number):
            if number % i == 0:
                state = False
                break
        return state

def isPrime2(number): #Works well with big numbers that are prime   
    d = 2
    while d*d <= number:
        while (number % d) == 0:            
            number //= d
        d += 1
    if number > 1:       
        return True
    else:
        return False`

Answer 1

Exhaustive division until the square root is about the simplest you can think of. Its worst case is for primes, as all divisions must be performed. Anyway, until a billion, there is virtually no measurable time (about 1.2 ms for 1000000007).

def FirstPrimeFactor(n):
    if n & 1 == 0:
        return 2
    d= 3
    while d * d <= n:
        if n % d == 0:
            return d
        d= d + 2
    return n

Note that this version returns the smallest divisor rather than a boolean.

Some micro-optimizations are possible (such as using a table of increments), but I don' think they can yield large gains.

There are much more sophisticated and faster methods available, but I am not sure they are worth the fuss for such small n.