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):
"""Test if any elements of primes divides 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):
"""Return a list of primes below the input argument."""
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 (inclusivly) 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.