Prime Numbers

Prime Numbers#

A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. Prime numbers are the building blocks of all natural numbers because every number can be expressed as a product of primes.

Steps:#

The steps to determine if a number \(n\) is prime are as follows:

  1. Check divisibility by 2: If \(n\) is even and greater than 2, it is not prime.

  2. Check divisibility by odd numbers: Test if \(n\) is divisible by any odd number from 3 up to \(\sqrt{n}\).

  3. Prime if no divisors found: If no divisors other than 1 and \(n\) are found, then \(n\) is prime.

For example, to check if 29 is a prime number:

  1. 29 is not even.

  2. Check divisibility by odd numbers up to \(\sqrt{29} \approx 5.39\) (i.e., check 3 and 5).

  3. 29 is not divisible by 3 or 5.

  4. Therefore, 29 is a prime number.

Hide code cell source 
import sympy as sp
from sympy import *
from math import gcd

Introduction to Prime Numbers#

Checking if number is prime or not#

To check if a number is prime or not, we need to check if it is divisible by any number other than 1 and itself. We can do this by iterating over all numbers from 2 to the square root of the number and checking if the number is divisible by any of them. If the number is divisible by any number other than 1 and itself, then it is not prime.

def is_prime(n):
    if n <= 1:
        print(f"The number {n} is not prime")
        return False
    for i in range(2, int(sp.sqrt(n)) + 1):
        if n % i == 0:
            print(f"The number {n} is not prime")
            return False
    print(f"The number {n} is prime")
    return True

Explanation

Checking if \(6\) is Prime:

  1. \(6\) is even.

  2. Since $\( is greater than \)2$ and even, it is not a prime number.

Checking if \(69769\) is prime or not#

n = 69769
is_prime(n)

The number 69769 is not prime

False

Explanation

Checking if \(69769\) is Prime:

  1. \(69769\) is not even.

  2. Calculate \(\sqrt{69769} \approx 264.17\). Check for divisibility by odd numbers up to \(264\).

  3. \(69769\) is divisible by \(263\):

\[ 69769 \div 263 = 265 \]

Checking if \(83\) is prime or not#

n = 83
is_prime(n)

The number 83 is prime

True

Explanation

Checking if 83 is Prime:

  1. 83 is not even.

  2. Calculate \(\sqrt{83} \approx 9.11\). Check for divisibility by odd numbers up to \(9\).

  3. \(83\) is not divisible by \(3, 5, or 7\).

  4. Therefore, \(83\) is a prime number.

Checking if \(983\) is prime or not#

n = 983
is_prime(n)

The number 983 is prime

True

Explanation

Checking if \(983\) is Prime:

  1. \(983\) is not even.

  2. Calculate \(\sqrt{983} \approx 31.36\). Check for divisibility by odd numbers up to \(31\).

  3. \(983\) is not divisible by \(3, 5, 7, 11, 13, 17, 19, 23, 29, or 31\).

  4. Therefore, \(983\) is a prime number.

Generating Prime Numbers#

To generate a random prime number, we can generate a random number and check if it is prime using the method described above. If the number is not prime, we can generate another random number and repeat the process until we find a prime number.

With this function, we can actually specify the range of prime numbers we want to generate. For example, if we want to generate a prime number between 1 and 20, we can specify this in the generate prime function.

def generate_prime_number(start=1000, end=10000):
    while True:
        n = random.randint(start,end)
        if is_prime(n):
            return n

p = generate_prime_number(1000,10000)
print(f"p = {p}")

The number 3939 is not prime
The number 6812 is not prime
The number 4209 is not prime
The number 5468 is not prime
The number 1843 is not prime
The number 5847 is not prime
The number 1110 is not prime
The number 5683 is prime
p = 5683

p = generate_prime_number(10000, 100000)
print(f"p = {p}")

The number 69497 is prime
p = 69497

p = generate_prime_number(10000, 100000)
print(f"p = {p}")

The number 29375 is not prime
The number 36854 is not prime
The number 21716 is not prime
The number 96230 is not prime
The number 39050 is not prime
The number 90887 is prime
p = 90887

Another Method for generating prime numbers:#

Another method for this uses the sympy library in Python. The sympy library provides a function called sympy.isprime that generates the nth prime number. We can use this function to generate prime numbers.

def generate_prime(start=100000, end=800000):
    while True:
        num = random.randint(start, end)
        if sp.isprime(num):
            return num

p = generate_prime(1000,10000)
print(f"p = {p}")

p = 8353

p = generate_prime(10000,1000000)
print(f"p = {p}")

p = 427369

p = generate_prime(2,20)
print(f"p = {p}")

p = 17

Generating a range of prime numbers:#

Here is a slight modification that allows us to print all prime numbers in a given range. We can use the sympy.primerange function to generate all prime numbers in a given range.

def generate_primes_in_range(start=2, end=20):
    return list(sympy.primerange(start, end))

def print_range(start, end):
    primes = generate_primes_in_range(start, end)
    print(f"Primes in range {start} to {end} are: {primes}")

start = 1
end = 20
print_range(start, end)

Primes in range 1 to 20 are: [2, 3, 5, 7, 11, 13, 17, 19]

start = 1
end = 100
print_range(start, end)

Primes in range 1 to 100 are: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

start = 100
end = 300
print_range(start, end)

Primes in range 100 to 300 are: [101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293]
Contents