Pythonism

code and the oracular

Prime Numbers in Python Video

leave a comment »

I just did this vid on Primes in Python, which is my top ranking popst here…

and here is the script

#  how to find prime numbers with Python



#  part 1 -  The Rectangle Game        



#  some numbers can be pictured as rectangles (or squares, which count too)



#  4 can be shown as         

          ##                
          ##                



#  8 can be shown as         

          ####              
          ####

#          or                

           ##               
           ##               
           ##               
           ##               



#  which are really the      
#   same because one is      
#   a rotation of the        
#        other               



# indeed some numbers can be drawn as rectangles in more than one way



# like 16 which can be

####
####
####
####



# or


##
##
##
##
##
##
##
##






#      but the number         
#            13               
#      cannot be drawn       
#      as a rectangle
#



# no matter how many different values you try for the width and height none will fit




####
####
####
#

# No!




######
######
#

# No!




###
###
###
###
#

# No!



# etc





# so there are some numbers which can't be rectangles




# and that is because they cannot be divided
# into a whole-number width or length



# and a number that can't be divided by any number other
# than itself and 1 in this way is PRIME



# Primality = Rectangularity




# so rectangular numbers are never prime
# ... and if a number can be divided like this then it is COMPOSITE...


# to repeat
# if a whole number can't be divided into any smaller whole numbers then
# it is PRIME... 




# (NOW FOR THE CODE !!)



# how would you get python to draw a rectangle?



# two loops one inside the other, right




for width in range(5):
    for length in range(6):
        print "#",
    print



# that is helpful and leads us to the next step
# which is to reverse the process and see if we
# can get some code that finds out whether a given
# number can be a rectangle (ie composite) or not...
# if it can't be a rectangle then it is prime - bingo!



# there is a helpful operator in Python which is
# called Integer Division and is represented by a % sign



# this operator gives the remainder when an integer x is divided by a number n



# so it is written x % n



# example

13 % 2




# 2 gives a remainder of 1 when divided into 13




# example

14 % 2




# two goes into 14 and so the remainder is 0



# so if we want to know if a number can be rectangular
# we can use % to see, because if the remainder after division by n
# is zero then we know we can use n as a width of our rectangle
# and thus since n divides x then our number is not Prime



# so 14 is not prime because 2 goes into 14
# but when we try the same with 13 its different

13 % 2
13 % 3
13 % 4
13 % 5
13 % 6
13 % 7
13 % 8
13 % 9
13 % 10
13 % 11
13 % 12




# no number apart from 1 or 13 goes in without a remainder
# so to get python to check this property for any number we like
# just use a loop



x = 29

for fac in range(2,x):
    print x % fac




# this shows that 29 has no integers that don't,
# when divided into it, leave a remainder
# which is not surprising since we know by lookup it is prime



# try another one

x = 28

for fac in range(2,x):
    print x % fac






# while 28 does have zero remainders... 




# and that's more or less all that's required to test
# primality in code



# except we can now put it into a function for re-use

def isprime(x):
    for fac in range(2,x):
        if x % fac == 0:
            return False
    return True




# and try loads of numbers

for integer in range(2,50):
    if isprime(integer):
        print integer,"is prime"
    else:
        print integer,"is composite"




# the rest is fine tuning...
# once you can see that x is not divisible by 2
# you know that you don't need to check for any higher
# even numbers, so our code gets optimised to

def isprime(x):
    if x % 2 == 0:
        return False
    for fac in range(3,x,2):
        if x % fac == 0:
            return False
    return True




# ok that's better...



# one more thing. think about what happens when you divide



# you get the number that goes into x
# and the value that is the number of times it goes

# like 27 / 3 = 9




# you can quit the loop as soon as you find a factor
# so how high does the factor you test need to go?
# the smallest possible factor of any composite number is
# going to be 2, so the highest factor you can have
# must be  half the number




# but if you check for 2 then you don't need to carry on counting up
# the longest you will need to keep checking for just one factor
# is when the number is a square, like 9 or 16
# you'll never need to count higher




# so if there hasn't been a divisor by the time you get to
# root x in the iteration, there can't be any higher ones




# and so our function becomes

def isprime(x):
    if x % 2 == 0:
        return False
    for fac in range(3,int(x**0.5)+1,2):
        if x % fac == 0:
            return False
    return True




# which is good enough for now




Advertisements

Written by Luke Dunn

December 30, 2015 at 5:15 pm

Posted in Math, Primes

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: