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

1. Algorithm 1 : 15 steps
2. Algorithm 2 : 8 steps
3. 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