As it is easy to get started, I first wrote a prime finding algorithm in Python. I used a very basic algorithm for this. I store a list of prime numbers, and I check the numbers less than the square root of the possible prime, if any are a factor of the number I’m checking, then it’s a composite, otherwise I append it to the list of prime numbers.
The code for this is on my Box account here.
This way, I only check for prime factors and I check the least possible numbers as if there are any factors, then some will be less than the square root.
Here is the code for the _test
function that contains this algorithm:
def _test(self, possible_prime)
prime = True
for i in self.primes:
if (i > math.sqrt(possible_prime)):
break
if (possible_prime % i) == 0:
prime = False
break
if (prime):
self.primes.append(possible_prime)
There are two other methods in my Prime
class; primes_below(self, limit)
and primes_number_of(self, limit)
. These are methods to get either all primes below a number or a specific number of primes. Here is the code for both of these:
def primes_below(self, limit)
i = self.primes[len(self.primes) - 1]
if (i == 2):
i += 1
else:
i +=2
while i <= limit:
self._test(i)
i += 2
return self.primes
In this, I get the last member of the list of primes and increment either to two or to the next odd number. This is because self.primes
is initialised to [2]
. Then I check only odd numbers to cut down on time and use the _test
function I have described earlier.
The other function runs in much the same way except the loop runs until the length of self.primes
is equal to limit
.
If this file is run, then it asks what mode you want (looping till you give it a satisfactory answer) then runs the method you wanted and gives you the output. Here is that code:
if __name__ == "__main__":
type = -1
while (type != 0 and type != 1):
question = "Do you want number of primes [0]"
question += ", primes below a number[1]?\n"
type = input(question)
limit = 1
print("")
if (type == 0):
limit = input("How many primes do you want?\n")
else:
limit = input("Primes (inclusively) below what number?\n")
t_start = time.time()
calculator = Prime()
if (type == 0):
primes = calculator.primes_number_of(limit)
end_calc = time.time()
msg = "\n"
if (limit < 1000):
msg += "The first " + str(limit) + " primes are:\n" + str(primes) + "\n"
msg += "The " + str(limit) + "th primes is: " + str(primes[-1])
print(msg)
else:
if (type == 1):
primes = calculator.primes_below(limit)
else:
assert(False)
end_calc = time.time()
msg = "\n"
if (limit < 1000):
msg += "The primes below " + str(limit) + " are:\n" + str(primes) + "\n"
msg += "There are " + str(len(primes)) + " primes below " + str(limit)
msg += "\nThe largest of which is: " + str(primes[-1])
print(msg)
print("\nCalculation time:"),
print(str(end_calc-t_start))
You’ll notice that when this is run, it will return the calculation time. This is because I was interested in a comparison between Python and C++ for this task. The difference in speed (which I will publish in a later post) was such that for large computational tasks, I will only use Python for an indication of the result or if it’s something I can just run overnight. The next part: C++ and the Sieve of Eratosthenes.
The full code for this is on my Box account here.