## Prime Numbers in Python Video

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

## Leave a Reply