Python Recap – II
Madhavan Mukund
https://www.cmi.ac.in/~madhavan
Programming, Data Structures and Algorithms using Python
Week 1
Checking primality
A prime number n has exactly two
factors, 1 and n
Note that 1 is not a prime
Madhavan Mukund Python Recap – II PDSA using Python Week 1 2/5
Checking primality
A prime number n has exactly two
factors, 1 and n def factors(n):
Note that 1 is not a prime fl = [] # factor list
for i in range(1,n+1):
Compute the list of factors of n
if (n%i) == 0:
fl.append(i)
return(fl)
Madhavan Mukund Python Recap – II PDSA using Python Week 1 2/5
Checking primality
A prime number n has exactly two
factors, 1 and n def factors(n):
Note that 1 is not a prime fl = [] # factor list
for i in range(1,n+1):
Compute the list of factors of n
if (n%i) == 0:
n is a prime if the list of factors is fl.append(i)
precisely [1,n] return(fl)
def prime(n):
return(factors(n) == [1,n])
Madhavan Mukund Python Recap – II PDSA using Python Week 1 2/5
Counting primes
List all primes upto m
def primesupto(m):
pl = [] # prime list
for i in range(1,m+1):
if prime(i):
pl.append(i)
return(pl)
Madhavan Mukund Python Recap – II PDSA using Python Week 1 3/5
Counting primes
List all primes upto m
def primesupto(m):
List the first m primes pl = [] # prime list
Multiple simultaneous assignment
for i in range(1,m+1):
if prime(i):
pl.append(i)
return(pl)
def firstprimes(m):
(count,i,pl) = (0,1,[])
while (count < m):
if prime(i):
(count,pl) = (count+1,pl+[i])
i = i+1
return(pl)
Madhavan Mukund Python Recap – II PDSA using Python Week 1 3/5
Counting primes
List all primes upto m
def primesupto(m):
List the first m primes pl = [] # prime list
Multiple simultaneous assignment
for i in range(1,m+1):
if prime(i):
for vs while pl.append(i)
Is the number of iterations known in return(pl)
advance?
Ensure progress to guarantee def firstprimes(m):
termination of while (count,i,pl) = (0,1,[])
while (count < m):
if prime(i):
(count,pl) = (count+1,pl+[i])
i = i+1
return(pl)
Madhavan Mukund Python Recap – II PDSA using Python Week 1 3/5
Computing primes
Directly check if n has a factor between def prime(n):
2 and n − 1 result = True
for i in range(2,n):
if (n%i) == 0:
result = False
return(result)
Madhavan Mukund Python Recap – II PDSA using Python Week 1 4/5
Computing primes
Directly check if n has a factor between def prime(n):
2 and n − 1 result = True
for i in range(2,n):
Terminate check after we find first
if (n%i) == 0:
factor
result = False
Breaking out of a loop return(result)
def prime(n):
result = True
for i in range(2,n):
if (n%i) == 0:
result = False
break # Abort loop
return(result)
Madhavan Mukund Python Recap – II PDSA using Python Week 1 4/5
Computing primes
Directly check if n has a factor between def prime(n):
2 and n − 1 result = True
for i in range(2,n):
Terminate check after we find first
if (n%i) == 0:
factor
result = False
Breaking out of a loop break # Abort loop
Alternatively, use while return(result)
def prime(n):
(result,i) = (True,2)
while (result and (i < n)):
if (n%i) == 0:
result = False
i = i+1
return(result)
Madhavan Mukund Python Recap – II PDSA using Python Week 1 4/5
Computing primes
Directly check if n has a factor between import math
2 and n − 1 def prime(n):
(result,i) = (True,2)
Terminate check after we find first while (result and (i <= math.sqrt(n))
factor if (n%i) == 0:
Breaking out of a loop result = False
i = i+1
Alternatively, use while
return(result)
Speeding things up slightly
Factors occur in pairs
√
Sufficient to check factors upto n
√
If n is prime, scan 2, . . . , n instead
of 2, . . . , n − 1
Madhavan Mukund Python Recap – II PDSA using Python Week 1 4/5
Properties of primes
There are infinitely many primes
Madhavan Mukund Python Recap – II PDSA using Python Week 1 5/5
Properties of primes
There are infinitely many primes
How are they distributed?
Madhavan Mukund Python Recap – II PDSA using Python Week 1 5/5
Properties of primes
There are infinitely many primes
How are they distributed?
Twin primes: p, p + 2
Madhavan Mukund Python Recap – II PDSA using Python Week 1 5/5
Properties of primes
There are infinitely many primes
How are they distributed?
Twin primes: p, p + 2
Twin prime conjecture
There are infinitely many twin primes
Madhavan Mukund Python Recap – II PDSA using Python Week 1 5/5
Properties of primes
There are infinitely many primes
How are they distributed?
Twin primes: p, p + 2
Twin prime conjecture
There are infinitely many twin primes
Compute the differences between
primes
Madhavan Mukund Python Recap – II PDSA using Python Week 1 5/5
Properties of primes
There are infinitely many primes
How are they distributed?
Twin primes: p, p + 2
Twin prime conjecture
There are infinitely many twin primes
Compute the differences between
primes
Use a dictionary
Start checking from 3, since 2 is the
smallest prime
Madhavan Mukund Python Recap – II PDSA using Python Week 1 5/5
Properties of primes
There are infinitely many primes def primediffs(n):
lastprime = 2
How are they distributed?
pd = {} # Dictionary for
Twin primes: p, p + 2 # prime diferences
for i in range(3,n+1):
Twin prime conjecture if prime(i):
There are infinitely many twin primes d = i - lastprime
Compute the differences between lastprime = i
primes if d in pd.keys():
pd[d] = pd[d] + 1
Use a dictionary else:
pd[d] = 1
Start checking from 3, since 2 is the
return(pd)
smallest prime
Madhavan Mukund Python Recap – II PDSA using Python Week 1 5/5
