I’m trying to do a simple primality test in Python.
Accoding to Wikipedia, a primality test is the following:
Given an input number n, check whether any integer m from 2 to n − 1 divides n. If n is divisible by any m then n is composite, otherwise it is prime.
I started with ruling out the even numbers – with the exception of 2 – as candidates to prime
def prime_candidates(x): odd = range(1, x, 2) odd.insert(0, 2) odd.remove(1) return odd
Then writing a function to check for primes, according to the rules above.
def isprime(x): for i in range(2, x-1): if x % i == 0: return False else: return True
And this is the main function, which iterates over a list of 8000 prime candidates and tests their primality
def main(): end = 8000 candidates = prime_candidates(end) for i in candidates: if isprime(i) and i < end: print 'prime found ' + str(i)
The problem is that the isprime
function returns True for numbers that aren’t primes.