Click here to Skip to main content
13,003,102 members (57,578 online)
Click here to Skip to main content
Add your own
alternative version


3 bookmarked
Posted 4 Nov 2012

Finding Primes: Part II – A Python Implementation

, 4 Nov 2012
Rate this:
Please Sign up or sign in to vote.
A Python implementation of finding primes

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)):
        if (possible_prime % i) == 0:
            prime = False
    if (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
        i +=2
    while i <= limit:
        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
    if (type == 0):
        limit = input("How many primes do you want?\n")
        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])
        if (type == 1):
            primes = calculator.primes_below(limit)
        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("\nCalculation time:"),

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.




About the Author

David Corne
Software Developer
United Kingdom United Kingdom



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

Coding Sites

  • BitBucket where I keep the majority of my projects.



  • coderwall and coderbits two profile compilation websites.

Social Sites

You may also be interested in...


Comments and Discussions

-- There are no messages in this forum --
Permalink | Advertise | Privacy | Terms of Use | Mobile
Web02 | 2.8.170626.1 | Last Updated 4 Nov 2012
Article Copyright 2012 by David Corne
Everything else Copyright © CodeProject, 1999-2017
Layout: fixed | fluid