$30
CECS 229: Programming Assignment #2
CECS 229: Programming Assignment #2
Submission Instructions:
To receive credit for this assignment you must submit to CodePost this file converted to a Python script named pa2.py
Objectives:
Use the Sieve of Eratosthenes to find all primes in a given range.
Design a computational algorithm for finding the Bézout coefficients of two integers.
Use Bézout coefficients to calculate the GCD.
Problem 1:
Create a function primes(a, b) that uses the Sieve of Eratosthenes to find all the primes p
satisfying a≤p≤b
. You may not use any built-in functions that perform entire or part of this algorithm.
INPUT:
a - a positive integer greater than or equal to 1 (raise a ValueError if an integer less than 1 is given), that is the lower bound
b - a positive integer greater than or equal to a (raise a ValueError if b < a)
OUTPUT:
a set of all the primes p
satisfying a ≤p≤
b
EXAMPLE:
>> primes(1, 10)
{2, 3, 5, 7}
>> primes(50, 100)
{53, 59, 61, 67, 71, 73, 79, 83, 89, 97}
Note: the order of the elements might be different in your output, and that is okay! As long as you have all the primes.
# Writing a function to find all the prime numbers between two numbers using Sieve of Eratosthenes
def primes(a, b):
# Writing conditional statements to raise ValueErrors for certain types of inputs
if a < 1:
# Raising valueError for Lower Bound(a)
raise ValueError("The lower bound must be greater than or equal to 1")
elif b < a:
# Raising valueError for Upper Bound(b)
raise ValueError("The upper bound must be greater than or equal to the lower bound")
else: # Continuing with the code if the inputs are valid
# Preparing an boolean array of all primes up to the square root of b
upper_bound = int(b ** 0.5) # Finding the upper-bound for the boolean array
all_primes = [True] * (upper_bound + 1) # The Boolean Array
# Setting values of 0 and 1 to False(they are not prime nor composite)
all_primes[0] = all_primes[1] = False
smallest_prime = 2 # The smallest prime number is 2
# Finding all the primes up to the square root of b
for i in range(smallest_prime, int(upper_bound) + 1):
if all_primes[i] == True:
for j in range(i * i, upper_bound + 1, i): # Marking all the multiples of i as False
all_primes[j] = False
# Array to store actual values of the prime numbers between a and b
prime_nums = []
sieve_range = [True] * (b - a + 1) # Boolean array to store the prime numbers between a and b
# Finding all the primes between a and b
for i in range(2, upper_bound + 1):
if all_primes[i]:
# Starting point of sieve/root out multiples of i
starting_point = max(i * i, ((a + i - 1) // i) * i)
# Marking all the multiples of i as False
for j in range(starting_point, b + 1, i):
sieve_range[j - a] = False
# Converting "TRUE" primes to their actual values
for i in range(len(sieve_range)):
if sieve_range[i] and i + a > 1:
prime_nums.append(i + a)
return set(prime_nums) # Returning the prime numbers between a and b as a set
Problem 2:
Create a function bezout_coeffs(a, b) that computes the Bezout coefficients s and t of a and b.
INPUT:
a,b - distinct integers
OUTPUT: {a: s, b: t} - dictionary where keys are the input integers and values are their corresponding Bezout coefficients.
EXAMPLE: >> bezout_coeffs(414, 662)
{414 : 8, 662 : -5}
HINT:
To come up with an algorithm for the function bezout_coeff(a,b) consider the following example:
Suppose a=13,b=21
. We seek s
and t
such that gcd (13,21)=13s+21t
Let's begin by defining s0=1,t0=0,a1=13,b1=21
. At every round in attempting to attain the gcd, we will refer to si
and ti
as the current coefficients of 13 and 21, respectively.
Round 1:
21=1⋅13+8
⟹8=21−1⋅13
We will call this EQN 1
⟹s1=−1,t1=1
NOTICE:
s1=−(b1 div a1)=−(21 div 13)=−1
Round 2:
a2=8,b2=13
13=1⋅8+5
⟹5=13−1⋅8
=1⋅13−1(21−1⋅13)
from EQN 1
=2⋅13−1⋅21
⟹s2=2,t2=−1
NOTICE:
s2=s0−s1(b2 div a2)
=1−1(13 div 8)
=1−(−1)(1)
=2
t2=t0−t1(b2 div a2)
=0−1(13 div 8)
=0−1(1)
=−1
Round 3:
a3=5,b3=8
8=1⋅5+3
⟹3=8−1b3 div a3⋅5
=1⋅(1t1⋅21−1s1⋅13)−1b3 div a3(2s2⋅13−1t2⋅21)
=−3⋅13+2⋅21
⟹s3=−3,t3=2
NOTICE:
s3=s1−s2(b3 div a3)
=−1−(2)(1)
=−3
t3=t1−t2(b3 div a3)
=1−(−1)(1)
=2
⋮
Round k
:
For any round k≥2
, the corresponding sk
and tk
values are given by
sk=sk−2−sk−1(bk div ak)
tk=tk−2−tk−1(bk div ak)
You should verify for yourself that for any a,b
,
s0=1
t0=0
s1=−(b div a)
t1=1
# Writing a function to find the bezout coefficients of two numbers
def bezout_coeffs(a, b):
# Variables to store the current and updated values of a and b
value_a, value_b = abs(a), abs(b) # Using absolute values to avoid negative a & b values
# Variables to store the current and updated values of the 1st & previous round coefficients of a and b
first_coeff_a, first_coeff_b = 1, 0
# Variables to store the current and updated values of the 2nd & next round coefficients of a and b
second_coeff_a, second_coeff_b = 0, 1
# Creating a loop to go through the rounds of coefficients until b is 0
while value_b != 0:
# Integer division of a and b
quotient = value_a // value_b
# Modulo of a and b
remainder = value_a % value_b
# Calculating the new coefficients of a and b
new_coeff_a = first_coeff_a - quotient * second_coeff_a
new_coeff_b = first_coeff_b - quotient * second_coeff_b
# Updating the values of a and b
value_a = value_b
value_b = remainder
# Updating the previous and next round coefficients of a
first_coeff_a = second_coeff_a
second_coeff_a = new_coeff_a
# Updating the previous and next round coefficients of b
first_coeff_b = second_coeff_b
second_coeff_b = new_coeff_b
return {a: first_coeff_a, b: first_coeff_b} # Returning the coefficients of a and b as a dictionary
Problem 3:
Create a function gcd(a, b) that computes the greatest common divisor of a and b using the bezout_coeff function you implemented for problem 2 lecture. No credit will be given to functions that employ any other implementation. For example, using the built-in function math.gcd() as part of our implementation will not receive any credit.
INPUT:
a,b - integers
OUTPUT: d - the gcd
EXAMPLE: >> gcd(414, 662)
2
HINT
The GCD of any two numbers must be positive by definition.
# Writing a function to find the greatest common divisor of two numbers
def gcd(a,b):
# Calling the bezout_coeffs function to find the coefficients of a and b
a_b_coeffs = bezout_coeffs(a, b)
s_coeff_a = a_b_coeffs[a] # Coefficient of a -> s
t_coeff_b = a_b_coeffs[b] # Coefficient of b -> t
# Calculating the greatest common divisor of a and b
GCD = abs((a * s_coeff_a) + (b * t_coeff_b)) # Following the Bezout Identity: |a*s + b*t| = gcd(a,b)
return GCD # Returning the greatest common divisor of a and b
Testing Your Functions
You can test your functions by running the cell below and verifying that your answers agree with the expected outcomes.
YOU MUST COMMENT OUT THE CELL BELOW PRIOR TO SUBMITTING ON CODEPOST
""" TESTER CELL: YOU MUST COMMENT THIS CELL OUT PRIOR TO SUBMITTING ON CODEPOST """
'''
print("\nTesting primes(1, 10)\nResult:", primes(1, 10), "\nExpected: {2, 3, 5, 7}")
print("\nTesting primes(2, 37)\nResult:", primes(2, 37), "\nExpected: {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}")
print("\nTesting primes(2, 100)\nResult:", primes(2, 100), "\nExpected: {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}")
print("\nTesting bezout_coeffs(414, 662)\nResult:", bezout_coeffs(414, 662), "\nExpected: {414: 8, 662: -5}")
print("\nTesting bezout_coeffs(26, 7)\nResult:", bezout_coeffs(26, 7), "\nExpected: {26: 3, 7: -11}")
print("\nTesting gcd(101, 4620)\nResult:", gcd(101, 4620), "\nExpected: 1")
print("\nTesting gcd(1011, 4620)\nResult:", gcd(1011, 4620), "\nExpected: 3")
print("\nTesting gcd(2349, 36)\nResult:", gcd(2349, 36), "\nExpected: 9")
'''
Testing bezout_coeffs(414, 662)
Result: {414: 8, 662: -5}
Expected: {414: 8, 662: -5}
Testing bezout_coeffs(26, 7)
Result: {26: 3, 7: -11}
Expected: {26: 3, 7: -11}
Testing gcd(101, 4620)
Result: 1
Expected: 1
Testing gcd(1011, 4620)
Result: 3
Expected: 3
Testing gcd(2349, 36)
Result: 9
Expected: 9
Testing gcd(414, 662)
Result: 2
Expected: 2
