Kernel: Python 3 (system-wide)

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 ( $\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.

#### Solution Procedures:

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

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

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 [0]: