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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | 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) |
This is a function that generates a list of prime numbers up to a given number.
Here’s a brief explanation of how the function works:
- The function takes a single argument, “givenNumber”, which is the number up to which the prime numbers should be generated.
- The “primes” list is initialized to an empty list and will be used to store the prime numbers.
- The outer for loop iterates over the range of numbers from 2 to “givenNumber” + 1.
- The “isPrime” variable is initialized to True for each number in the range and is used to determine whether the number is prime or not.
- The inner for loop iterates over the range of numbers from 2 to the current number in the outer loop. If any of these numbers divide the current number evenly (i.e., the remainder is 0), then “isPrime” is set to False.
- If “isPrime” is still True after the inner loop finishes executing, then the current number is prime and it is appended to the “primes” list.
- When the outer loop finishes executing, the function returns the “primes” list.
Approach 2: For Loops with Break
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | 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) |
This is a function that generates a list of prime numbers up to a given number.
This function is similar to the “approach1” function, with the exception of a “break” statement being added to the inner for loop.
Here’s a brief explanation of how the function works:
- The function takes a single argument, “givenNumber”, which is the number up to which the prime numbers should be generated.
- The “primes” list is initialized to an empty list and will be used to store the prime numbers.
- The outer for loop iterates over the range of numbers from 2 to “givenNumber” + 1.
- The “isPrime” variable is initialized to True for each number in the range and is used to determine whether the number is prime or not.
- The inner for loop iterates over the range of numbers from 2 to the current number in the outer loop. If any of these numbers divide the current number evenly (i.e., the remainder is 0), then “isPrime” is set to False and the loop is broken.
- If “isPrime” is still True after the inner loop finishes executing, then the current number is prime and it is appended to the “primes” list.
- When the outer loop finishes executing, the function returns the “primes” list.
Approach 3: For Loop, Break, and Square Root
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | 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) |
This is a function that generates a list of prime numbers up to a given number.
This function is similar to the “approach2” function, with the exception of the range of numbers being used in the inner for loop.
Here’s a brief explanation of how the function works:
- The function takes a single argument, “givenNumber”, which is the number up to which the prime numbers should be generated.
- The “primes” list is initialized to an empty list and will be used to store the prime numbers.
- The outer for loop iterates over the range of numbers from 2 to “givenNumber” + 1.
- The “isPrime” variable is initialized to True for each number in the range and is used to determine whether the number is prime or not.
- The inner for loop iterates over the range of numbers from 2 to the square root of the current number in the outer loop, plus 1. If any of these numbers divide the current number evenly (i.e., the remainder is 0), then “isPrime” is set to False and the loop is broken.
- If “isPrime” is still True after the inner loop finishes executing, then the current number is prime and it is appended to the “primes” list.
- When the outer loop finishes executing, the function returns the “primes” list.
By limiting the range of numbers in the inner loop to the square root of the current number, the function can more efficiently determine whether the number is prime or not. This is because if a number “n” has a divisor greater than the square root of “n”, then it must also have a divisor less than the square root of “n”. Therefore, we only need to check for divisors up to the square root of “n”.
The performance difference can be measured using the the timeit library which allows you to time your Python 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.
1 2 3 4 5 6 7 8 9 | import timeit # Approach 1: Execution time print(timeit.timeit('approach1(500)', globals=globals(), number=10000)) # Approach 2: Execution time print(timeit.timeit('approach2(500)', globals=globals(), number=10000)) # Approach 3: Execution time print(timeit.timeit('approach3(500)', globals=globals(), number=10000)) |
Clearly Approach 3 is the fastest.
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.
