Technical Blog

# Finding Primes: Part II – A Python Implementation

, 4 Nov 2012 CPOL
 Rate this:
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&#8217;m checking [...]

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.

## Share

Software Developer
United Kingdom
I am a C++ developer with a strong interest in Python, C#, and Qt. I work on a native C++ application which uses COM to call C# in order to use a WPF GUI.

While I develop an application using WPF exclusivly for windows, I am a big linux user. My favourite distro at the moment is Linux Mint, and I love the delights of the command line,.

If you've read something of mine and you enjoyed it, check out my blog.

I am also active on various other sites, listed below.

### Coding Sites

• BitBucket where I keep the majority of my projects.
• GitHub where I have a few older projects. This includes my current long term project, I'm writing a book about design patterns in python. Find the repository here and blog posts about individual patterns here
• Stackoverflow I'm not too active on stackoverflow, I'm more of a listener.
• coderwall and coderbits two profile compilation websites.