CoCalc Public Filesclean / Project / Project1 / Project_final.ipynbOpen with one click!
Authors: Kriscel Berrum, Melaney Cutler, Roger Thelwell
Views : 59
Compute Environment: Ubuntu 18.04 (Stable)

Math 248 Project 1

A Prime Problem

Kriscel Berrum and Melaney Cutler

Problem statement:

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 (55=1\frac{5}{5} = 1) or to divide it by 1 (51=5\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.

Solution Procedures:

We will go over the three programs being run below:

  1. 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 n\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
    
  2. 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.

    video: https://www.khanacademy.org/computing/computer-science/cryptography/comp-number-theory/v/sieve-of-eratosthenes-prime-adventure-part-4

    Gif: https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

  3. 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.

Time Test

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

Code:

Naive

In [1]:
#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

In [2]:
#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

In [3]:
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

In [4]:
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

In [5]:
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)
count=1 and integer=15 on step 13 count=2 and integer=825 on step 14 count=3 and integer=725 on step 5 count=4 and integer=1925 on step 6 count=5 and integer=2275 on step 11 count=6 and integer=425 on step 1 count=7 and integer=390 on step 2 count=8 and integer=330 on step 10 count=9 and integer=290 on step 5 count=10 and integer=770 on step 6 count=11 and integer=910 on step 11 count=12 and integer=170 on step 1 count=13 and integer=156 on step 2 count=14 and integer=132 on step 10 count=15 and integer=116 on step 5 count=16 and integer=308 on step 6 count=17 and integer=364 on step 11 count=18 and integer=68 on step 1 count=19 and integer=4 on step 9 count=20 and integer=30 on step 13 count=21 and integer=225 on step 13 count=22 and integer=12375 on step 14 count=23 and integer=10875 on step 5 count=24 and integer=598125 on step 14 count=25 and integer=525625 on step 5 count=26 and integer=1395625 on step 6 count=27 and integer=1649375 on step 11 count=28 and integer=308125 on step 1 count=29 and integer=282750 on step 2 count=30 and integer=750750 on step 6 count=31 and integer=140250 on step 1 count=32 and integer=128700 on step 2 count=33 and integer=113100 on step 5 count=34 and integer=300300 on step 6 count=35 and integer=56100 on step 1 count=36 and integer=51480 on step 2 count=37 and integer=45240 on step 5 count=38 and integer=38280 on step 10 count=39 and integer=33640 on step 5 count=40 and integer=89320 on step 6 count=41 and integer=105560 on step 11 count=42 and integer=19720 on step 1 count=43 and integer=18096 on step 2 count=44 and integer=48048 on step 6 count=45 and integer=8976 on step 1 count=46 and integer=3344 on step 3 count=47 and integer=2024 on step 4 count=48 and integer=8360 on step 7 count=49 and integer=5060 on step 4 count=50 and integer=20900 on step 7 [2]

Time Test

but first editing code so there aren't any print outs, just True or False

In [6]:
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
In [7]:
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}")
Time required for Naive 0.0604703426361084 Time required for Naive alternative approach 1 0.020005464553833008 Time required for Naive alternative approach 2 0.0017209053039550781 Time required for Sieve of Eratosthenes 4.7295708656311035 Time required for not Sieve of Eratosthenes 4.7295708656311035

Naive time Graph

In [8]:
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")
Text(0, 0.5, 'Runtime')

Sieve of Eratosthenes Graphs

In [9]:
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")
Time required for Sieve of Eratosthenes 4.7295708656311035
Text(0, 0.5, 'Runtime')
In [10]:
#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")
Time required for Sieve of Eratosthenes 4.7295708656311035
Text(0, 0.5, 'Runtime')
In [ ]: