# 15-112: Fundamentals of Programming and Computer Science Class Notes: Loops

1. 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!"
``````

2. nthHappyPrime Example
See #2 from here.