Skip to content
Econowmics
Menu
  • Home
  • Economics
    • Econometrics
    • Economics and History
    • Macroeconomics
    • Microeconomics
    • Miscellaneous
      • Awards and Honors
      • Economic Schools of Thought
      • Economic Quotes
      • Economic Videos
    • Terms and Concepts
  • Cognitive Biases
  • Data Analysis
    • Statistics
    • Python Programming
  • Contact
Menu

[Python] Prime number generator

Posted on

God may not play dice with the universe, but something strange is going on with the prime numbers.

Paul Erdos

 

prime number calculation main
Photo by Markus Spiske from Pexels

 

A prime number is a positive number greater than 1, which has no positive integer divisors except 1 and itself.  Therefore, numbers like 2, 3, 5, 7, 11 are all prime numbers.

As a result of the definition of a prime number, one might probably decide to check if a given number, x, is prime by trying to divide it by all the integers starting from 2 and smaller than x. If no such number divides x evenly, then it can be concluded that x is a prime number. Although such a method can be used for very small numbers, but it will be very time consuming and also subject to errors for large numbers. For instance, if x=100,000,000, then the program must check each and every number between 2 and 99,999,999 to see if it divides x evenly or not.

Better methods can nevertheless be used to calculate prime numbers. One of the most efficient algorithms for calculating prime numbers is called Sieve of Eratosthenes. Put simply, this algorithm starts from the very first prime number, 2, and marks every multiple of it smaller than x as composite. Then the algorithm continues with the next prime number. The remaining numbers will be primes. The following animation, adapted from Wikipedia, clearly illustrates this algorithm.

 

prime number calculation method

 


Let’s have a quick look at the code which does this for us:

[pastacode lang=”python” manual=”%0A%0A%0A%22%22%22Econowmics.com%22%22%22%0A%0Adef%20Sieve(n)%3A%0A%20%20%20%20%22%22%22This%20function%20calculates%20all%20prime%20numbers%20up%20to%20a%20given%20limit(n)%22%22%22%0A%20%20%20%0A%20%20%20%20%23Defining%20the%20inintial%20list%2C%20all%20equal%20to%20True%0A%20%20%20%20primes%20%3D%20%5BTrue%20for%20i%20in%20range(n%2B1)%5D%0A%20%20%20%20primes%20%5B0%5D%20%3D%20primes%20%5B1%5D%20%3D%20False%0A%0A%20%20%20%20%23The%20starting%20number%0A%20%20%20%20p%20%3D%202%0A%0A%20%20%20%20%23Running%20a%20loop%20to%20check%20all%20numbers%20below%20the%20square%20root%20of%20the%20given%20number%0A%20%20%20%20while%20p%20**%202%20%3C%20n%3A%0A%20%20%20%20%20%20%20%20%23Check%20to%20see%20if%20it%20is%20equal%20to%20True%20(if%20the%20number%20is%20prime%20or%20not)%0A%20%20%20%20%20%20%20%20if%20primes%5Bp%5D%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%23If%20it%20was%20a%20prime%20number%2C%20kill%20every%20other%20multiple%20of%20it%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20number%20in%20range(p*2%2C%20n%2B1%2C%20p)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20primes%5Bnumber%5D%20%3D%20False%0A%0A%20%20%20%20%20%20%20%20%23Increment%20the%20starting%20number%20by%20one%20to%20keep%20the%20loop%20working%0A%20%20%20%20%20%20%20%20p%20%2B%3D%201%20%0A%0A%20%20%20%20prime_numbers%20%3D%20%5Bi%20for%20i%20in%20range%20(n%2B1)%20if%20primes%5Bi%5D%3D%3DTrue%5D%0A%20%20%20%20%23If%20you%20want%20to%20see%20the%20list%20of%20prime%20numbers%20in%20the%20output%0A%20%20%20%20%23return%20prime_numbers%0A%0A%20%20%20%20%23If%20you%20want%20to%20see%20how%20many%20prime%20numbers%20are%20there%20in%20a%20given%20range%0A%20%20%20%20return%20len(prime_numbers)” message=”” highlight=”” provider=”manual”/]

 

First, we define a list equal to the size of n, with all elements equal to True. As the algorithm runs, those indexes of this list that are marked as composite will be changed to False. Before the loop, we set the first two instances, namely 0 and 1, which are not primes, into False.

Then, we define the starting number, p=2.

In the next step, we start a loop to check all the numbers below the square root of the number we are looking for. The reason why we only check the numbers below the square root can be seen from this photo:

prime number, square root
The factors repeat themselves after the square root of the given number.

After the square root, the numbers just repeat themselves and it would be of no use to check the other numbers.

Now, if the number in the index that we are checking is actually a prime, we set all of its multiples as composite, i.e. set them to False (not primes).

Then we increment p by 1 to check the next number. This goes on until the condition of the while-loop turns False.

In the last step, we can return the result that we want. For example, here two options are given. Depending on each one suits you best, you have to uncomment it. Here, we check for the total amount of primes less than a given number.

Let’s test the function:

[pastacode lang=”python” manual=”import%20time%0A%0A%23marking%20the%20starting%20time%0Astart%20%3D%20time.time()%0A%0A%23For-loop%20to%20evaluate%20the%20function%0Afor%20i%20in%20%5B10%2C100%2C1000%2C10000%2C100000%2C1000000%2C10000000%2C100000000%5D%3A%0A%20%20%20%20print%20(%22There%20are%20%22%20%2B%20str(Sieve(i))%20%2B%20%22%20prime%20numbers%20below%20%22%20%2B%20str(i)%20%2B%20%22.%22)%0A%0A%23marking%20the%20end%20of%20time%20and%20calculating%20the%20total%20duration%20%20%0Aend%20%3D%20time.time()%0Aduration%20%3D%20end%20-%20start%0Aprint%20(duration)” message=”” highlight=”” provider=”manual”/]

 

Which results in:

prime number calculation result

 

 

Also watch

 

 

Further reading on prime numbers

The Largest Known prime by Year: A Brief History

Prime Numbers–Why are They So Exciting?

How Many Primes are There?

Why Prime Numbers Still Surprise and Mystify Mathematicians

unusual and physical methods for finding prime numbers

 

Related posts:

[Python] Greatest Common Factor
[Python] Happy numbers
[Python] Penalty Kicks Simulator
[Python] Palindrome Checking Function
[Python] Binary Search

Anything in here will be replaced on browsers that support the canvas element

  • Amos Tversky
  • Daniel Kahneman
  • cognitive bias
  • Milton Friedman
  • Wealth of Nations
  • Nobel Prize Laureate
  • Adam Smith
  • 20:20 ratio
  • law of small numbers
  • the halo effect
  • wealth inequality
  • income inequality
  • Law of Large Numbers
  • Dow Jones Industrial Average
  • status quo bias
  • Behavioral Economics
  • daniel kahnemann
  • hyperinflation
  • the gambler's fallacy
  • gambler's fallacy
©2023 Econowmics | Design: Newspaperly WordPress Theme