Efficiency Code : Prime Number
Efficiency Code¶
In this writing, i will describe about efficiency code by counting at the number of step to do the task.
We will not determine efficiency by the duration of the code, because different computer may give different running time.
I will add "+1 step" for every process given in the code.
The processes are :
- define variabel / overwrite variable
- example : x=2, y=True
- conditional : comparing variabel
- example : 2==3, x>y, x!y, ...
- printing
- example : print(y)
- etc
However, given the circumtances, i will omit some processes.
Recording Step¶
See the code below, how many steps are reuired to do the processes?
In [1]:
print('0')
print('1')
print('2')
print('3')
print('4')
print('5')
print('6')
print('7')
print('8')
print('9')
print('10')
# this code takes 11 steps
0 1 2 3 4 5 6 7 8 9 10
In [2]:
#Printing integer number for 0 to n
for i in range(11):
print(i)
# this code takes 11 steps
0 1 2 3 4 5 6 7 8 9 10
In [3]:
#Printing integer number for 0 to n
#record number of steps to do the task
step=0
for i in range(11):
print(i)
step=step+1
print("number of steps =",step)
# this code takes "11" steps
0 1 2 3 4 5 6 7 8 9 10 number of steps = 11
The actual step for the last code is 22, because we have another process, that is the process step=step+1
However the "step=0" and the "step=step+1" will be ignored as a process, it is just a variable that help us to calculate the steps.
Later, we will omit the "print(...)", so we only focus on define/overwrite and conditional
In [4]:
#Recording example 2
step=0
x=5
y=6
print("check whether x=y?")
step=step+1
if(x==y):
print("Hello")
else:
print("World")
print("number of steps =",step)
check whether x=y? World number of steps = 1
Efficiency Example 1 : Printing Even Number¶
In [5]:
#Printing even number for 0 to n
step=0
n=10
for i in range(n+1): #the step for creating range is omitted
step=step+1 #+1 step because of conditional : "determine whether the number is even"
if (i%2==0):
print(i)
step=step+1 #+1 step because of print
print("number of steps =",step)
0 2 4 6 8 10 number of steps = 17
In [6]:
import math
#Printing even number for 0 to n
step=0
n=10
for i in range(0,math.ceil((n+1)/2)): #the step for creating range and calculating ceil is omitted
print(i*2)
step=step+1 #+1 because of print
print("number of steps =",step)
0 2 4 6 8 10 number of steps = 6
In [7]:
import math
#Printing even number for 0 to n
step=0
n=10
for i in range(0,n+1,2): #the step for creating range is omitted
step=step+1 #+1 step for every loop
print(i)
print("number of steps =",step)
0 2 4 6 8 10 number of steps = 6
The second and third code is more efficient
Efficiency Example 2 : Prime Number¶
Natural number $p$ is called a prime number, if it could not write as $p=a\times b$ with $a$ and $b$ is a natural number which is smaller than $p$ and greater than 1
Example :
- 12 is a product of 3 and 4, so 12 is not a prime number
- 15 is a product of 3 and 5, so 15 is not a prime number
- 13 is a prime number, because there are not exist natural number $a$ and $b$ smaller than $p$ that satisfy $p=a\times b$
In other word, natural number $p$ is not a prime number if exist a natural number $c$, which satisfy $p$ modulo $c$ is 0
Algorithm 1 :
- given a number : $p$
- check :
- if p is divisible by 2, then p is not a prime number. (break/finish) if not divisible then ...
- if p is divisible by 3, then p is not a prime number. (break/finish) if not divisible then ...
- if p is divisible by 4, then p is not a prime number. (break/finish) if not divisible then ...
- if p is divisible by 5, then p is not a prime number. (break/finish) if not divisible then ...
- if p is divisible by 6, then p is not a prime number. (break/finish) if not divisible then ...
- ...
- Check until the divider = $p-1$
- If p is divisible by one number from $\{2,3,4,5,6,...,p-1\}$, then $p$ is not a prime number.
In [8]:
p=17
In [9]:
#given p
print("p =",p)
#checking if p is a prime number
#assume statement q : "p is a prime number" is TRUE
q=True
i=2
while q==True and i<p: #i={2,3,...,p-1}
print("Checking whether",p,"is divisible by",i)
if p%i==0: #checking if p is divisible by i
q=False #"p is a prime number" is FALSE --> "p is not a prime number"
print(p,"is divisible by",i)
i=i+1
print("")
print("p is a prime number" if q else "p is not a prime number")
p = 17 Checking whether 17 is divisible by 2 Checking whether 17 is divisible by 3 Checking whether 17 is divisible by 4 Checking whether 17 is divisible by 5 Checking whether 17 is divisible by 6 Checking whether 17 is divisible by 7 Checking whether 17 is divisible by 8 Checking whether 17 is divisible by 9 Checking whether 17 is divisible by 10 Checking whether 17 is divisible by 11 Checking whether 17 is divisible by 12 Checking whether 17 is divisible by 13 Checking whether 17 is divisible by 14 Checking whether 17 is divisible by 15 Checking whether 17 is divisible by 16 p is a prime number
Lets record the steps
In [10]:
#record the steps
step = 0
#given p
print("p =",p)
#checking if p is a prime number
#assume statement q : "p is a prime number" is TRUE
q=True
i=2
while q==True and i<p: #i={2,3,...,p-1}
#step=step+1 #+1 step for every loop
step=step+1 #+1 step because of conditional : "determine whether p divisible by i"
print(step,". Cheking whether",p,"is divisible by",i)
if p%i==0: #checking if p is divisible by i
q=False #"p is a prime number" is FALSE --> "p is not a prime number"
print(p,"is divisible by",i)
i=i+1
print("")
print("p is a prime number" if q else "p is not a prime number")
print("number of steps =",step)
p = 17 1 . Cheking whether 17 is divisible by 2 2 . Cheking whether 17 is divisible by 3 3 . Cheking whether 17 is divisible by 4 4 . Cheking whether 17 is divisible by 5 5 . Cheking whether 17 is divisible by 6 6 . Cheking whether 17 is divisible by 7 7 . Cheking whether 17 is divisible by 8 8 . Cheking whether 17 is divisible by 9 9 . Cheking whether 17 is divisible by 10 10 . Cheking whether 17 is divisible by 11 11 . Cheking whether 17 is divisible by 12 12 . Cheking whether 17 is divisible by 13 13 . Cheking whether 17 is divisible by 14 14 . Cheking whether 17 is divisible by 15 15 . Cheking whether 17 is divisible by 16 p is a prime number number of steps = 15
Algorithm 2 :
The difference is, if $p$ is not divisible by 2, then off course $p$ not divisible by greater even number (4,6,8,...)
- given a number : $p$
- check :
- if p is divisible by 2, then p is not a prime number. (break/finish) if not divisible then ...
- if p is divisible by 3, then p is not a prime number. (break/finish) if not divisible then ...
- if p is divisible by 5, then p is not a prime number. (break/finish) if not divisible then ...
- if p is divisible by 7, then p is not a prime number. (break/finish) if not divisible then ...
- ...
- Check until the divider = $p-2$
- If p is divisible 2 or odd number $\{3,5,7,...,p-2\}$, then $p$ is not a prime number.
In [11]:
#Algorithm 2
#record the steps
step = 0
#given p
print("p =",p)
#checking if p is a prime number
#assume statement q : "p is a prime number" is TRUE
q=True
i=2
step=step+1 #cheking if p is divisible by i=2
print(step,". Cheking whether",p,"is divisible by",i)
if p % i==0:
print(q,"is divisible by",i)
q=False #"p is a prime number" is FALSE --> "p is not a prime number"
else:
i=3
while q==True and i<p: ##looping for every odd number {3,5,7,...,p-2}
#step=step+1 #+1 step for every loop
step=step+1 #+1 step because of conditional : "determine whether p divisible by i"
print(step,". Cheking whether",p,"is divisible by",i)
if p%i==0: #checking if p is divisible by i
q=False #"p is a prime number" is FALSE --> "p is not a prime number"
print(p,"is divisible by",i)
i=i+2 #+2 because the divider is odd number
print("")
print("p is a prime number" if q else "p is not a prime number")
print("number of steps =",step)
p = 17 1 . Cheking whether 17 is divisible by 2 2 . Cheking whether 17 is divisible by 3 3 . Cheking whether 17 is divisible by 5 4 . Cheking whether 17 is divisible by 7 5 . Cheking whether 17 is divisible by 9 6 . Cheking whether 17 is divisible by 11 7 . Cheking whether 17 is divisible by 13 8 . Cheking whether 17 is divisible by 15 p is a prime number number of steps = 8
Before we go to Algorithm 3, wee need to know this fact
Given a positive integer $n>1$
If $n=a\times b$ with $a,b$ positive integer grater than 1,
Then $a<=\sqrt{n}$ and $b>=\sqrt{n}$
Example 1:
- $32=1\times 32$
- $32=2\times 16$
- $32=4\times 8$
Example 2:
- $100=1\times 100$
- $100=2\times 50$
- $100=4\times 25$
- $100=5\times 5$
Example 3:
- $24=1\times 24$
- $24=2\times 12$
- $24=3\times 8$
- $24=4\times 6$
Algorithm 3 :
After cheking if $p$ is divisible by 2, we check if $p$ is divisible by odd number, just until rounded up ($\sqrt{p}$) or ceil($\sqrt{p}$)
- given a number : $p$
- check :
- if p is divisible by 2, then p is not a prime number. (break/finish) if not divisible then ...
- if p is divisible by 3, then p is not a prime number. (break/finish) if not divisible then ...
- if p is divisible by 5, then p is not a prime number. (break/finish) if not divisible then ...
- if p is divisible by 7, then p is not a prime number. (break/finish) if not divisible then ...
- ...
- Check until the divider = $ceil(\sqrt{p})$
- If p is divisible 2 or odd number $\{3,5,7,...,ceil(\sqrt{p})\}$, then $p$ is not a prime number.
In [12]:
import math
#Algorithm 3
#record the steps
step = 0
#given p
print("p =",p)
#checking if p is a prime number
#assume statement q : "p is a prime number" is TRUE
q=True
i=2
step=step+1 #cheking if p is divisible by i=2
print(step,". Cheking whether",p,"is divisible by",i)
if p % i==0:
print(q,"is divisible by",i)
q=False #"p is a prime number" is FALSE --> "p is not a prime number"
else:
i=3
while q==True and i<=math.sqrt(p): ##looping for every odd number {3,5,7,...,floor(\sqrt(p))}
#step=step+1 #+1 step for every loop
step=step+1 #+1 step because of conditional : "determine whether p divisible by i"
print(step,". Cheking whether",p,"is divisible by",i)
if p%i==0: #checking if p is divisible by i
q=False #"p is a prime number" is FALSE --> "p is not a prime number"
print(p,"is divisible by",i)
i=i+2 #+2 because the divider is odd number
print("")
print("p is a prime number" if q else "p is not a prime number")
print("number of steps =",step)
p = 17 1 . Cheking whether 17 is divisible by 2 2 . Cheking whether 17 is divisible by 3 p is a prime number number of steps = 2
Checking Prime Number Comparations¶
For checking if 17 is a prime number
- Algorithm 1 : 15 steps
- Algorithm 2 : 8 steps
- Algorithm 3 : 2 steps
The third is far more efficient, lets try for checking a greater integer
Home work :)¶
Find a more efficient algorithm for checking wheter an integer is a prime number, better than the third algorithm
Comments
Post a Comment