My First Steps with Python – Prime Numbers

I recently started studying the Python programming language. I’m getting ready for a new programming-related position next year and one of my colleagues suggested using Python as part of it. I’ve heard of Python more and more over the past several years and I figured now would be as good a time as any to finally learn it.

I can definitely recommend Udemy’s Complete Python Bootcamp by Jose Portilla. This course is written for complete programming beginners and does an excellent job of introducing the fundamentals and guiding the student through various programming concepts. It’s probably more basic than I actually need but it never hurts to go back to school.

One of my standard exercises with a programming language is to write a short program to generate prime numbers (numbers divisible only by 1 and themselves). It’s a relatively simple problem solving test that involves math, decisions, variables and looping statements. There are also a number of algorithms that can be used to generate prime numbers so there’s plenty of opportunity to experiment. Once, I even had a competition with a co-worker to see who could generate the most primes in a set time (he won).

I started out with a fairly straightforward method –

The code starts by defining a range of 2 to 200,000 and assuming each number is prime until proven otherwise. It then uses a second range of numbers from 2 to the square root of the number being evaluated (num**0.5 produces a square root in Python). If any of these division operations leave a remainder of 0 (num % testNum), that means the number is not prime and the program moves on to the next number to be evaluated. Otherwise, the number is added to the list of primes.

I was fairly happy with myself when I got this to work in my newest programming language but I’ve also learned a certain amount of humility over the years and part of that is to assume that there is probably a better way out there that I haven’t thought of but someone else has. A quick Google search of StackOverflow revealed a much shorter way with Python’s All() function.

In one line, the All() function iterates through all the calculations with a given range of values. In this case, it says “Divide num by all values of testNum where testNum is between 2 and the integer of num’s square root plus 1. I add 1 here because Python’s Range() function defines the range as everything¬†up to but excluding the second value. Also, many of the square roots will be floating point values and will be shortened by the Int() conversion.

In Python circles, this method would be considered more¬†Pythonic than mine because it’s shorter and simpler.

It’s also much, much faster. Check out the results in Jupyter notebook. I’ve imported the timeit module elsewhere to time the execution.

My standard approach vs. Python's All() function.

My standard approach vs. Python’s All() function. (Click for larger view.)

Both methods generated 17,984 prime numbers but the All() function did it in 2.85 seconds compared to the 15.89 seconds of my method. That’s a pretty staggering difference for a relatively small run.

I’m on my way to really enjoying Python and this was a great little learning session. I’m glad to have tried it my way first; not only was it a good exercise with some of the Python syntax but it also provided an excellent comparison between methods appropriate to other languages and what Python has to offer.

 

Leave a Reply

Your email address will not be published. Required fields are marked *