We are looking for three programs to either determine if a number is prime or generate a prime number that fits a set criterion. A prime number is a number that only has two divisors, 1 and itself. An example is the number 5. The only way to divide 5 and get a whole number is to divide it by 5 ($\frac{5}{5} = 1$) or to divide it by 1 ($\frac{5}{1} = 5$). Prime numbers are so often used because they have a significant impact on the mathematical world. They allow for security in computer programs and also serve as a foundation for math theorists’ studies. For these reasons, we want to find a way to quickly determine if a number is prime.
We will go over the three programs being run below:
A Naive function will determine if a number, n, is prime by dividing n by all integers smaller than n. This is a very tedious process especially when it comes to large numbers. Not every number smaller than n needs to be checked. In reality, if you start after 1, any number that divides n with no remainder (and is not n) would tell you that n is not a prime number, and therefore meaning, you do not have to check any more numbers smaller than n.
We started by defining a function that will contain all values for n. We want to show that if a number has more than 2 divisors it is not prime.
def Alln(n):
divisors = 1
if n == 1:
print (f"{n} is not prime")
for i in range(1,n):
x = n % i
if x == 0:
divisors += 1
Next, we want to try to run the code again, but much faster. We can do this by decreasing the number of integers and stopping our search with a break line after reaching a divisor that does not satisfy composite number requirements, thus proving it is a prime number.
for i in range(2,n):
x = n % i
if x == 0:
divisors += 1
if divisors >1:
break
Another method to a faster code is to use the biggest divisor. If the biggest divisor of $\sqrt{n}$ does not return a value of 1 or n, it is not prime.
def approach2(n):
big_divisor = math.floor(math.sqrt(n))
if n ==1:
return False
for i in range(2,1+big_divisor):
if n % i == 0:
return False
return True
Sieve of Eratosthenes is a program that finds all prime numbers that are smaller than number n. Sieve of Eratosthenes looks at all numbers between 1 and n and determines whether or not the number is prime. The program does so by starting at the first unmarked number, 2, since it is prime and then crosses out the numbers that are multiples of said primes number because we know they are composite once all nonprime numbers have been crossed out, there is a list of only prime numbers remaining.
We first ran the previous code from Part 1 that found prime numbers by only dividing it by some numbers smaller than n, but modified it to return either "True" or "False" for prime numbers instead of printing out words.
for i in range(2,n):
x = n % i
if x == 0:
divisors += 1
if divisors >1:
break
if divisors == 0:
return True
else :
return False
Next, we imported the math and numpy packages to be able to use the remove operation. After defining our function, Sieve, we went through a list in range of 2 through n and removed all none prime numbers we computed the prime numbers starting with the first prime number through our chosen value of N.
def Sieve(N):
Nlist =list(range(2,N))
for i in range (2,N):
if "call previous function for i" == "check if its not prime":
Nlist.remove(i)
return Nlist
Although this does not check for muliples of prime numbers it does use the idea of making a list smallar. The first time we attempted to write this program we made a version of Seive that created a list using append instead of utilizing an already created list and using remove to get ride of none prime numbers. However it does not matter since they run at the same speed.
Conway’s Prime Producing Machine is a list of 14 rational numbers that are used to produce prime numbers. You input 2 in the machine and the machine goes down the list until 2 is multiplied by one of the list items and an integer is returned the next step would be to use that new integer in the machine until another integer is produced. The machine also checks to see if the integer is a pure power of 2, if so the exponent is a prime.
Simulation for understanding: https://dms.umontreal.ca/~andrew/conwaymachine.html
We started this by defining all variables and creating a list for the machine. Next, we created a loop to go through the machine. Within that loop the we test if the set integer when mulitplied by a number in the machine produces an integer. In the second loop we test if the integer is a pure power of 2.
while count < 50:
for i in range(len(machine)):
if abs(int(integer * machine[i]) - integer*machine[i])< tolx:
integer = int(integer * machine[i])
break
count+=1
if int(math.log2(integer)) == math.log2(integer):
p = int(math.log2(integer))
Primes.append(p)
print
However our code gets stuck when integer equals 8 and does not add 3 to a list of primes the only number it will add is 2. We were not able to figure out why that was.
After running these three programs we ran a speed test to determine the faster method to find prime numbers.
To find the amount of time that passed when running the code, we needed to import the time package. Following that, we constructed a base code that begins the time clock, calls the appropriate function, runs it, and then ends the time clock. Finally, it finds the time passed by subtracting the end time from the start time.
import time
start1 = time.time()
for i in range (1,1000):
FunctionName(i)
end1 = time.time()
total = end1-start1
print
The second alternative approach using the biggest divisor was the fastest way to find out if N is prime taking 0.00096 seconds and the first method being the slowest taking 0.03869 seconds. The Sieve of Eratosthenes took 0.03869 seconds
Naive
#Naive program to find if n is prime by dividng n by **all** integers **smaller** than n def Alln(n): #setting divisor to 1 because were checking for numbers smaller than n and n can always be divided by it's self divisors = 1 if n == 1: print (f"{n} is not prime") for i in range(1,n): x = n % i if x == 0: divisors += 1 if divisors == 2: print(f"{n} is a prime number, it only has {divisors} divisors") else : print (f"{n} has {divisors} divisors, not prime")
Alternative approach
#faster Naive program Finding if n is prime by dividng n by **some** integers **smaller** than n stoping when another divisor is found that's not 1 or it's self def Somen(n): #starting at 0 because were ignoring 1 and n since we already know that those are divisors of all numbers divisors = 0 if n == 1: print (f"{n} is not prime") #return false for i in range(2,n): x = n % i if x == 0: divisors += 1 if divisors >1: break if divisors == 0: print(f"{n} is a prime number, it only has 2 divisors") #return True else : print (f"{n} is not prime, its has more than 2 divisors") #return False
Second alternative approach
import math ##### **Different approach** # biggest divisor of the square root of n gives us a number that is not 1 or n therefore, not prime def approach2(n): big_divisor = math.floor(math.sqrt(n)) if n == 1: #print (f"{n} is not prime") return False for i in range(2,1+big_divisor): if n % i == 0: return False return True
Sieve of Eratosthenes
import math import numpy as np def Somen2(n): #starting at 0 because were ignoring 1 and n since we already know that those are divisors of all numbers divisors = 0 for i in range(2,n): x = n % i if x == 0: divisors += 1 if divisors >1: break if divisors == 0: return True else : return False def Sieve(N): Nlist =list(range(2,N)) #Sieve of Eratosthenes only accounts for 2 through N-1 #if you want to include 1 and N change range(2,N) to range(1,N+1) for i in range (2,N): if Somen2(i) == False: Nlist.remove(i) return Nlist def notSieve(N): Primes=[] #Sieve of Eratosthenes only accounts for 2 through N-1 #if you want to include 1 and N change range(2,N) to range(1,N+1) for i in range (2,N): if Somen2(i): Primes.append(i) return Primes
Conway's Prime Producing Machine
import math machine =[17/91 , 78/85, 19/51 , 23/38 , 29/33 , 77/29 , 95/23 , 77/19 , 1/17 ,11/13 , 13/11, 15/14 , 15/2 , 55/1] Primes=[] Primes2=[] p = 0 integer = 2 count = 0 tolx = 1e-12 while count < 50: a = 0 for i in range(len(machine)): a += 1 #print(i) # nice to check the break command if abs(int(integer * machine[i]) - integer*machine[i])< tolx: integer = int(integer * machine[i]) break count+=1 print(f'count={count} and integer={integer} on step {a}') if int(math.log2(integer)) == math.log2(integer): p = int(math.log2(integer)) Primes.append(p) print(Primes)
Time Test
but first editing code so there aren't any print outs, just True or False
def Alln2(n): #setting divisor to 1 because were checking for numbers smaller than n and n can always be divided by it's self divisors = 1 for i in range(1,n): x = n % i if x == 0: divisors += 1 if divisors == 2: return True else : return False #Computing all prime numbers smaller than N import math import numpy as np
import time ## Naive start1 = time.time() for i in range (1,1000): Alln2(i) end1 = time.time() total = end1-start1 print (f"Time required for Naive {total}") #Naive alternative approach 1 start2 = time.time() for i in range (1,1000): Somen2(i) end2 = time.time() total2 = end2-start2 print (f"Time required for Naive alternative approach 1 {total2}") #Naive alternative approach 2 start3 = time.time() for i in range (1,1000): approach2(i) end3 = time.time() total3 = end3-start3 print (f"Time required for Naive alternative approach 2 {total3}") #Sieve of Eratosthenes start4 = time.time() for i in range (1,1000): Sieve(i) end4 = time.time() total4=end4-start4 print (f"Time required for Sieve of Eratosthenes {total4}") #Not Sieve of Eratosthenes start5 = time.time() for i in range (1,1000): notSieve(i) end5 = time.time() total5=end5-start5 print (f"Time required for not Sieve of Eratosthenes {total4}")
Naive time Graph
import time from matplotlib import pyplot as plt import numpy as np #Sieve of Eratosthenes total1=np.zeros(1000) total2=np.zeros(1000) total3=np.zeros(1000) for i in range (1,1000): start1 = time.time() Alln2(i) end1 = time.time() total1[i]=end1-start1 for i in range (1,1000): start2 = time.time() Somen2(i) end2 = time.time() total2[i]=end2-start2 for i in range (1,1000): start3 = time.time() approach2(i) end3 = time.time() total3[i]=end3-start3 plt.plot(total1,'go') plt.plot(total2,'ro') plt.plot(total3,'bo') plt.xlabel('N value') plt.ylabel("Runtime")
Sieve of Eratosthenes Graphs
import time from matplotlib import pyplot as plt #Sieve of Eratosthenes total=np.zeros(1000) for i in range (1,1000): start4 = time.time() Sieve(i) end4 = time.time() total[i]=end4-start4 print (f"Time required for Sieve of Eratosthenes {total4}") plt.plot(total,'go') plt.xlabel('nth time Sieve has been called') plt.ylabel("Runtime")
#Not Sieve of Eratosthenes total2=np.zeros(1000) for i in range (1,1000): start5 = time.time() notSieve(i) end5 = time.time() total2[i]=end5-start5 print (f"Time required for Sieve of Eratosthenes {total4}") plt.plot(total2,'bo') plt.xlabel('nth time Not Sieve has been called') plt.ylabel("Runtime")