Write a program to generate a list of all prime numbers less than 20. Before starting it is important to note what a prime is. number A prime number has to be a positive integer Divisible by exactly 2 integers (1 and itself) 1 is not a prime number While there are many different ways to solve this problem, here are a few different approaches. Approach 1: For Loops # Initialize a listprimes = [] for possiblePrime in range(2, 21): # Assume number is prime until shown it is not. isPrime = True for num in range(2, possiblePrime): if possiblePrime % num == 0: isPrime = False if isPrime: primes.append(possiblePrime) If you look at the inner for loop enclosed in the red rectangle below, notice that as soon is False, it is inefficient to keep on iterating. It would be more efficient to exit out of the loop. isPrime Approach 2: For Loops with Break Approach 2 is more efficient than approach 1 because as soon as you find a given number isn’t a prime number you can exit out of loop using . break # Initialize a listprimes = []for possiblePrime in range(2, 21): # Assume number is prime until shown it is not. isPrime = True for num in range(2, possiblePrime): if possiblePrime % num == 0: isPrime = False break if isPrime: primes.append(possiblePrime) Approach 2 is much more efficient than approach 1. For example, if you look at the case when , notice that there is much less iteration in approach 2. possiblePrime = 15 Approach 3: For Loop, Break, and Square Root Approach 2 benefited from not doing unnecessary iterations in the inner for loop. Approach 3 is similar except the inner range function. Notice that the inner range function is now . range(2, int(possiblePrime ** 0.5) + 1) # Initialize a listprimes = []for possiblePrime in range(2, 21): # Assume number is prime until shown it is not. isPrime = True for num in range(2, int(possiblePrime \*\* 0.5) + 1): if possiblePrime % num == 0: isPrime = False break if isPrime: primes.append(possiblePrime) To explain why this approach works, it is important to note a few things. A composite number is a positive number greater than 1 that is not prime (which has other than 1 and itself). Every composite number has a factor less than or equal to its square root (proof ). For example, in the image of the factors of 15 below, notice that the factors in red are just the reverses of the green factors. In other words, by the commutative property of multiplication 3 x 5 = 5 x 3. You just need to include the green pairs to be sure that you have all the factors. factors here Factors of 15 Why Compare Different Approaches? An algorithm is simply a procedure for solving a problem. These approaches have different procedure for solving problems. Notably approach 3 has _Get a kick start on your career and ace your coding interviews!_www.udemy.com Python for Data Structures, Algorithms, and Interviews! Time Comparison of Different Approaches Certain methods to generate prime numbers are more efficient. To show this, let’s study time the performance difference between the approaches generating prime numbers up to a given number. Approach 1: For Loops def approach1(givenNumber): # Initialize a list primes = \[\] for possiblePrime in range(2, givenNumber + 1): # Assume number is prime until shown it is not. isPrime = True for num in range(2, possiblePrime): if possiblePrime % num == 0: isPrime = False if isPrime: primes.append(possiblePrime) return(primes) Approach 2: For Loops with Break def approach2(givenNumber): # Initialize a list primes = \[\] for possiblePrime in range(2, givenNumber + 1): # Assume number is prime until shown it is not. isPrime = True for num in range(2, possiblePrime): if possiblePrime % num == 0: isPrime = False break if isPrime: primes.append(possiblePrime) return(primes) Approach 3: For Loop, Break, and Square Root def approach3(givenNumber): # Initialize a list primes = \[\] for possiblePrime in range(2, givenNumber + 1): # Assume number is prime until shown it is not. isPrime = True for num in range(2, int(possiblePrime \*\* 0.5) + 1): if possiblePrime % num == 0: isPrime = False break if isPrime: primes.append(possiblePrime) return(primes) The performance difference can be measured using the the library which allows you to time your code. In this case, we are measuring the time it take find prime numbers up to 500 for each approach. The code below runs the code for each approach 10000 times and outputs the overall time it took in seconds. timeit Python import timeit # Approach 1: Execution timeprint(timeit.timeit('approach1(500)', globals=globals(), number=10000)) # Approach 2: Execution timeprint(timeit.timeit('approach2(500)', globals=globals(), number=10000)) # Approach 3: Execution timeprint(timeit.timeit('approach3(500)', globals=globals(), number=10000)) Clearly Approach 3 is the fastest. Algorithmic Comparison of Different Approaches An algorithm is simply a procedure or formula for solving a problem. These approaches have different procedures (algorithms) for generating prime numbers. In the previous section, we looked at the time it took to run each algorithm. The problem is the speed depends of the computer you are using. For this section, we will use Big O notation to compare algorithms. https://www.udemy.com/python-for-data-structures-algorithms-and-interviews/learn/v4/t/lecture/3179554?start=0 https://github.com/jmportilla/Python-for-Algorithms--Data-Structures--and-Interviews/blob/master/Algorithm%20Analysis%20and%20Big%20O/Big%20O%20Notation.ipynb https://www.udemy.com/python-for-data-structures-algorithms-and-interviews/learn/v4/t/lecture/3179552?start=0 If you are wondering what n is in these different approaches, n is the size of the input. In this case n is the size of the input of some sort. Approach 1 and 2 are O(n*n) Approach 3 is O(n*sqrt(n)) Sieve (maybe approach 5) O(n*log(log(n))) Concluding Remarks The three approaches are definitely not the only ways to calculate prime numbers, but hopefully the various ways of identifying prime numbers helped you. Prime numbers are important in number theory and cryptographic methods like the rsa algorithm. As always, the code in the post is also available on my github ( , ). If you any questions or thoughts on the tutorial, feel free to reach out in the comments below or through . approach code time comparison Twitter
