#
15-112: Fundamentals of Programming and Computer Science

Class Notes: Loops

**Loops**`# for loop over ranges def sumFromMToN(m, n): total = 0 for x in xrange(m, n+1): total += x return total assert(sumFromMToN(5, 10) == 5+6+7+8+9+10) # Actually, don't need a loop here... def sumFromMToN(m, n): return sum(xrange(m, n+1)) assert(sumFromMToN(5, 10) == 5+6+7+8+9+10) # What if we omit first parameter? def sumToN(n): total = 0 for x in xrange(n+1): total += x return total assert(sumToN(5) == 0+1+2+3+4+5) # we can add a third parameter to xrange, an optional step: def sumEveryKthFromMToN(m, n, k): total = 0 for x in xrange(m, n+1, k): total += x return total assert(sumEveryKthFromMToN(5, 20, 7) == (5 + 12 + 19)) # let's just add the odd numbers from m to n def sumOfOddsFromMToN(m, n): total = 0 for x in xrange(m, n+1): if (x % 2 == 1): total += x return total assert(sumOfOddsFromMToN(4, 10) == sumOfOddsFromMToN(5,9) == (5+7+9)) # Once again, without a conditional in the loop: def sumOfOddsFromMToN(m, n): if (m % 2 == 0): # m is even, add 1 to start on an odd m += 1 total = 0 for x in xrange(m, n+1, 2): total += x return total assert(sumOfOddsFromMToN(4, 10) == sumOfOddsFromMToN(5,9) == (5+7+9)) # And again, ranging in reverse (not wise in this case, but instructional) def sumOfOddsFromMToN(m, n): if (n % 2 == 0): # n is even, subtract 1 to start on an odd n -= 1 total = 0 for x in xrange(n, m-1, -2): # be careful here! total += x return total assert(sumOfOddsFromMToN(4, 10) == sumOfOddsFromMToN(5,9) == (5+7+9)) # And, of course, again in this case we don't need a loop! def sumOfOddsFromMToN(m, n): if (m % 2 == 0): m += 1 return sum(xrange(m, n+1, 2)) assert(sumOfOddsFromMToN(4, 10) == sumOfOddsFromMToN(5,9) == (5+7+9)) # we don't even need the conditional, but this is less clear and worse code def sumOfOddsFromMToN(m, n): return sum(xrange(m + (1 - m%2), n+1, 2)) # this works, but it's gross! assert(sumOfOddsFromMToN(4, 10) == sumOfOddsFromMToN(5,9) == (5+7+9)) # range versus xrange # in Python 3, there is no xrange! # in Python 2, xrange does not create a list, so is more efficient than range def compareRangeAndXrange(m, n, k): print "In compareRangeAndXrange, m =", m, ", n =", n, " k =", k print " xrange(m,n,k) =", xrange(m, n, k) print " sum(xrange(m,n,k)) =", sum(xrange(m,n,k)) if (len(range(m,n,k)) < 100): print " range(m,n,k) =", range(m, n, k) print " sum(range(m,n,k)) =", sum(range(m,n,k)) compareRangeAndXrange(5, 50, 6) # in Python 2, range and xrange similar here # compareRangeAndXrange(1, 10**9, 1) # but not here! # nested for loops def printCoordinates(xMax, yMax): for x in xrange(xMax+1): for y in xrange(yMax+1): print "(", x, ",", y, ") ", print printCoordinates(4, 5) # how about some stars? def printStarRectangle(n): # print an nxn rectangle of asterisks for row in xrange(n): for col in xrange(n): print "*", print printStarRectangle(5) # What would this do? Be careful and be precise! def printMysteryStarShape(n): for row in xrange(n): print row, for col in xrange(row): print "*", print printMysteryStarShape(5) # while loop def leftmostDigit(n): n = abs(n) while (n >= 10): n = n/10 return n assert(leftmostDigit(726584892345519990098) == 7) # Example: Find the Nth Positive Integer with Some Property # eg: find the nth number that is a multiple of either 4 or 7 def isMultipleOf4or7(x): return ((x % 4) == 0) or ((x % 7) == 0) def nthMultipleOf4or7(n): found = 0 guess = -1 while (found <= n): guess += 1 if (isMultipleOf4or7(guess)): found += 1 return guess print "Multiples of 4 or 7:", for n in xrange(15): print nthMultipleOf4or7(n), print # Misuse: Iterate Over a Range of Integers # sum numbers from 1 to 10 # note: this works, but you should not use "while" here. # instead, do this with "for" (once you know how) def sumToN(n): # note: even though this works, it is bad style. # You should do this with a "for" loop, not a "while" loop. total = 0 counter = 1 while (counter <= n): total += counter counter += 1 return total assert(sumToN(5) == 1+2+3+4+5) # Once again, but with a bug!: def buggySumToN(n): # note: this not only uses a "while" instead of a "for" loop, # but it also contains a bug. Ugh. total = 0 counter = 0 while (counter <= n): counter += 1 total += counter return total #assert(buggySumToN(5) == 1+2+3+4+5) # And once more, using a "for" loop (the right way!): def sumToN(n): total = 0 for counter in xrange(n+1): total += counter return total assert(sumToN(5) == 1+2+3+4+5) # break and continue print "Break and Continue example", for n in xrange(200): if (n % 3 == 0): continue # skips rest of this pass (generally not a good idea to use "continue") elif (n == 10): break # skips rest of entire loop print n, print # Infinite "while" loop with break def readUntilDone(): linesEntered = 0 while (True): response = raw_input("Enter a string (or 'done' to quit): ") if (response == "done"): break print " You entered: ", response linesEntered += 1 print "Bye!" return linesEntered linesEntered = readUntilDone() print "You entered", linesEntered, "lines (not counting 'done')." # isPrime # Note: there are faster/better ways. We're just going for clarity and simplicity here. def isPrime(n): if (n < 2): return False for factor in xrange(2,n): if (n % factor == 0): return False return True # And take it for a spin for n in xrange(500): if isPrime(n): print n, # fasterIsPrime #Note: this is still not the fastest way, but it's a nice improvement. def fasterIsPrime(n): if (n < 2): return False if (n == 2): return True if (n % 2 == 0): return False maxFactor = int(round(n**0.5)) for factor in xrange(3,maxFactor+1,2): if (n % factor == 0): return False return True # More concise fasterIsPrime def fasterIsPrime(n): if (n == 2): return True if ((n < 2) or (n % 2 == 0)): return False for factor in xrange(3,int(round(n**0.5))+1,2): if (n % factor == 0): return False return True # Verify these are the same for n in xrange(1000): if (isPrime(n) != fasterIsPrime(n)): print n assert(isPrime(n) == fasterIsPrime(n)) print "They seem to work the same!" # Now let's see if we really sped things up import time bigPrime = 499 # Try 1010809, or 10101023, or 102030407 print "Timing isPrime(",bigPrime,")", time0 = time.time() print ", returns ", isPrime(bigPrime), time1 = time.time() print ", time = ",(time1-time0)*1000,"ms" print "Timing fasterIsPrime(",bigPrime,")", time0 = time.time() print ", returns ", fasterIsPrime(bigPrime), time1 = time.time() print ", time = ",(time1-time0)*1000,"ms" # nthPrime def nthPrime(n): found = 0 guess = 0 while (found <= n): guess += 1 if (isPrime(guess)): found += 1 return guess # and let's see a list of the primes for n in xrange(10): print n, nthPrime(n) print "Done!"`

**nthHappyPrime Example**

See #2 from here.