I will be using Python to create this for a few reasons but the most important of these is that Python is very useful in the sense that it does not cap the size of a number you wish to store - which is vitally important for this program as the numbers will get very, very large. Before I start you may want to read some of my posts on basic programming in Python:
Fermat's little theorem is that ap-1/p always has a remainder of 1 for a prime p that is co-prime to a. And utilising this fact is how we check for a number being prime or not. One problem with Fermat's little theorem is that it can also occasionally work for when p is not actually prime (this is called a Poulet number), these are rare but to minimise the probability that the number isn't actually prime is to check the number with a different value of a multiple times.
Before we begin we need to be able to check what the highest common factor of two numbers actually is (in this case it will be a and p). To do this we will use the Euclidean algorithm, if you read that post it will tell you how to create that function and also what each part means. For the purposes of this program I will simply give you the code needed.
def gcd(a,b):Now we get down to the good bit and properly begin programming the prime checker!
while b != 0:
a, b = b, a%b
return a
def primecheck(num):We begin by creating a new user-defined function called 'primecheck', it will require one variable, which we will call 'num'. Python uses indentation to distinguish between different code segments and functions, so everything contained within the function will be indented. Three local variables will be required for the function, one to be used as a counter for when repeating Fermat's prime check to reduce the chance that the number is a Poulet number, one to be used as the 'a' in Fermat's little theorem and one to return whether the number is prime or not.
count = 0
a = 2
prime = True
if (num - 1)/6 == int((num-1)/6) and (num - 5)/6 == int(num - 5)/6):Now that we have the local variables for the function we can begin writing the code needed to check if a number is prime or not. The algorithm itself takes a fairly long time, so we want to begin by trying to get rid of numbers that are obviously not prime without needing to do very much to the number. All prime numbers (other than 2 and 3) can be written in the form 6n + 1 or 6n + 5 (why?), so we can check that our number satisfies this before we proceed with the more processor heavy check.
{Fermat's prime check}
else:
prime = False
return prime
If the number cannot be expressed in the form 6n + 1 with n as an integer then the check is stopped there and the number is returned as not being prime, if it does meet that criteria then the Fermat primality check is performed. After the prime check is performed the outcome is returned (whether prime is True or False).
while (count < 10):The check is performed 10 times with a different value of a to ensure that the number is not a Poulet prime, that is why there is a loop while count is less than 10. The loop starts by making a note that the check has been performed by increasing count by 1, a check is then performed to ensure that a and num are coprime, if they are not a is changed and the check is reperformed. Once a and num are coprime we utilise the pow function, pow(a,b,c) returns the remainder of ab/c; so in this code we are utilising this function to utilise Fermat's little theorem to check that num is prime by finding the remainder of anum - 1/num and if this is not 1 then the test has failed and num is immediately returned as false. If all the checks come back with no problems then num is returned as prime.
count = count + 1
while gcd(a, num) != 1: a = a + 1 if pow(a, num - 1, num) != 1: count = 10 prime = False a = a + 1
This is it for the coding of the actual prime checker, the rest of the programming is to give the program structure, variables and how to save the outcome of each check.
num = input("First prime to check ")To begin two variables are created for the first prime number to check and the last prime number to check in order to give the program an end point. While the number to be checked is less than the last number a check will be performed. A boolean variable prime is assigned to the output of the primecheck when performed on num. If prime is true then a text document called primes is opened to append and the number is added to it, read more on editing files from within Python. A message is displayed to the user to state whether the number is or is not prime. 2 is added to the previous number to ensure that the next number is odd, this relies on the fact that the first number entered was also odd, if it was not then you would be checking whether or not only even numbers are prime which obviously they will not be (except 2).
lastnum = input("Last prime to check ")
while num <= lastnum:
prime = primecheck(num)
if prime == True:
FILE = open("primes.txt", "a")
FILE.write(str(num))
FILE.write(", ")
FILE.close()
print num," is prime."
else:
print num, " is not prime."
num = num + 2
And that is it for the whole program! Hopefully yours is now working correctly, if you have any problems please leave a comment and I will help you as soon as I can. If you haven't already you may wish to download my .exe prime checker, download my source code or you may want to download my list of the first 7,000,000 prime numbers created with this prime checker.
No comments:
Post a Comment