Generating Prime number with Python

Posted On February 7, 2023

Prime numbers are a fascinating topic in mathematics. They have many important applications in cryptography, coding theory, and number theory. In this blog post, we’ll introduce you to generating prime numbers with Python and show you how to get started.

What are Prime Numbers?

A prime number is a natural number greater than 1 that is only divisible by 1 and itself. For example, the first six prime numbers are 2, 3, 5, 7, 11, and 13.

Generating Prime Numbers

There are many algorithms for generating prime numbers, but the most straightforward method is to check each number in turn to see if it’s prime. To do this, we need to divide the number by all the positive integers less than itself and see if there are any other factors besides 1 and itself.

Here’s a simple Python function that generates prime numbers:

def is_prime(n):
    if n <= 1:
        return False
    for i in range(2, n):
        if n % i == 0:
            return False
    return True

def generate_primes(limit):
    primes = []
    for i in range(2, limit+1):
        if is_prime(i):
            primes.append(i)
    return primes

limit = 100
print(generate_primes(limit))

In this example, the is_prime function checks if a number n is prime by dividing it by all the positive integers less than itself and seeing if there are any other factors besides 1 and itself. The generate_primes function generates a list of all the prime numbers up to a specified limit. In this example, the limit is set to 100.

Optimizing the Algorithm

The prime number generation algorithm described above is simple, but it’s not very efficient. To optimize the algorithm, we can take advantage of the fact that a number can only be divided by primes that are less than or equal to its square root.

Here’s an optimized version of the prime number generation algorithm:

import math

def is_prime(n):
    if n <= 1:
        return False
    for i in range(2, int(math.sqrt(n))+1):
        if n % i == 0:
            return False
    return True

def generate_primes(limit):
    primes = []
    for i in range(2, limit+1):
        if is_prime(i):
            primes.append(i)
    return primes

limit = 100
print(generate_primes(limit))

In this optimized version of the algorithm, the is_prime function only checks the numbers up to the square root of n. This makes the algorithm much more efficient, especially for large values of n.

Unit Test

Following is a sample unit test for the code.

import unittest
import prime_number_generator

class TestPrimeNumberGenerator(unittest.TestCase):
    def test_is_prime(self):
        self.assertTrue(prime_number_generator.is_prime(2))
        self.assertTrue(prime_number_generator.is_prime(3))
        self.assertFalse(prime_number_generator.is_prime(4))
        self.assertTrue(prime_number_generator.is_prime(5))

    def test_generate_primes(self):
        self.assertEqual(prime_number_generator.generate_primes(10), [2, 3, 5, 7])
        self.assertEqual(prime_number_generator.generate_primes(20), [2, 3, 5, 7, 11, 13, 17, 19])
        self.assertEqual(prime_number_generator.generate_primes(2), [2])
        self.assertEqual(prime_number_generator.generate_primes(1), [])

if __name__ == '__main__':
    unittest.main()

In this example, we’re using the unittest module from the Python Standard Library to write unit tests for the is_prime and generate_primes functions from the prime_number_generator module. The tests check if the functions return the expected results for various inputs.

Conclusion

Generating prime numbers is a great way to get started with Python programming and explore the world of mathematics. Whether you’re a beginner or an experienced programmer, you’ll find that Python provides an easy and powerful way to generate prime numbers and explore their properties.