Comeau Software Solutions

Making sense of technology since 2000.

Menu
  • Home / Updates
  • Services / Contact Us
  • Rogue C# Project Page
  • More Resources
    • Join Ocala’s Tech Community!
    • YouTube Channel
    • Personal Site
Menu

My First Steps with Python – Prime Numbers

Posted on November 27, 2016November 9, 2022 by Andrew Comeau

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.

1 thought on “My First Steps with Python – Prime Numbers”

  1. michelle says:
    October 19, 2018 at 9:08 am

    Hello, I made some changes to your code, and I obtained a better time, 0.55 seconds.
    Here are the changes:
    primelist.append(2)
    for numbers in range(3, 200000):
    if numbers%2!=0 and all(numbers%divisors!=0 for divisors in range (3, int(numbers**0.5)+1,2)):
    primelist.append(numbers)
    So I excluded the even numbers from my all function and the step in range is 2, to also exclude even divisors.
    So its faster as it avoids a whole bunch of numbers to compare.

Comments are closed.

ComeauSoftware.com provides learning resources, including tutorials and videos, to guide you in understanding today's technology. Please check out our YouTube channel and bookmark this site to stay informed of upcoming projects.

Comeau Software Solutions also provides software consultation, including the development of database solutions, in Ocala, Florida. This includes rescuing Microsoft Access database projects and assistance in move to other solutions. Please contact us for more information on how we can help you with your project needs.

Available on Amazon.com


MagniPros 4X Large Ultra Bright LED Page Magnifier
Read even the small print with 400% magnification! Anti-glare lens with large viewing area and 12 dimmable LEDs

MagniPros
  • Articles
  • C#
  • Careers
  • Commentary
  • Database Design
  • Databases
  • Hardware
  • How-to
  • Humor
  • Internet
  • Jobs
  • Linux
  • Microsoft Access
  • MySQL
  • Ocala I.T. Professionals
  • Personal
  • Personal Tech
  • Programming
  • Resources
  • Reviews
  • Rogue C# Series
  • Software
  • SQL
  • Uncategorized
  • Web Design
  • Writing
©2023 Comeau Software Solutions | Theme by SuperbThemes