Click here to Skip to main content
Click here to Skip to main content
Technical Blog

Finding Primes: Part II – A Python Implementation

, 4 Nov 2012 CPOL
Rate this:
Please Sign up or sign in to vote.
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 [...]

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.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

David Corne
Software Developer
United Kingdom 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.

Social Sites

Follow on   Twitter   Google+

Comments and Discussions

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