View Single Post
Old 2020-01-09, 02:13   #15
Dylan14
 
Dylan14's Avatar
 
"Dylan"
Mar 2017

3×191 Posts
Default For loops part 2: The break and continue commands

So far, we just dealt with how for loops work on a high level, and we constructed a few ways to set up a loop (namely, using either an iterable object or a range object). But say we want to control a loop more succinctly, and in particular, we want to have a way to "escape". This can be done using the break and continue commands. We will apply these to an example that is very prevalent at mersenneforum: trial factoring of Mersenne numbers.

The break command:

Break is a very simple command: it breaks out of a loop (which can be a for loop or a while loop (*)). The syntax is as follows:

Code:
break
In psuedocode, this would look like this:

Code:
#stuff before the loop
for object in a sequence:
    #stuff to run in the loop
    if condition:
        break
        #then jump out the loop and then go to the next piece of code outside the loop
    #stuff following the break statement

#stuff after the loop
If one has a nested for loop, then a break will terminate the loop in which it appears, and move to the next iteration of the next inner loop.
Example of a break statement - one loop:
Code:
string = "mersenneforum"
for i in string:
    if i != "s":
        print(i)
    else:
        break
What this does is checks if a character in the string is not s. If it is not s, we print the character. Otherwise, we break out of the loop, and since nothing follows, execution stops.
Nested loops and break:
Code:
characters = "abcdefghijklmnopqrstuvwxyz"
for i in range(6):
     print("Outer loop iteration:" + str(i))
     for j in characters:
         print(j)
         if j == "c":
              print("Inner loop interrupted...")
              break
This code runs the outer loop, which prints the current iteration, and then the inner loop runs, which prints the alphabet up to c, and at that point the inner loop breaks, and we go to the next iteration of the outer loop.

The continue command:

The continue command is similar to the break command, but instead of leaving the loop, we skip whatever is left in the body of the loop and start the next iteration.
In psuedocode:
Code:
#stuff before the loop
for object in a sequence:
    #stuff to run in the loop
    if condition:
        continue
        #then go to the beginning of the code block in the loop
    #stuff after the continue statement
#stuff after the loop
The syntax is the same as with break.
Example with continue:
Code:
string = "mersenneforum"
for i in string:
    if i != "n":
        print(i)
    else:
        continue
Here, we check if the character is not n, and if it is not, we print the character. Otherwise, we go to the next letter in the string. The result is that we get all the characters in mersenneforum, one character at a time, except for the two n's in that.

An application: Mersenne trial factoring:
We can use for loops, the continue statement, and the break statement to create a simple program to trial factor Mersenne numbers (**).
First, some facts that we can use:
1. Factors of Mersennes must have the form 2*k*p+1, where p is the exponent, which is a prime number.
2. The factor must be 1 or 7 (mod 8). This reduces the search space quite a bit.
So how can we implement this? Well, the first statement tells us that we could iterate through all k's from some lower bound to some upper bound, via a for loop.
The second statement states that we should check if q = 2*k*p+1 is 1 or 7 mod 8 and if it isn't, discard it.
So we can code this:
Code:
#A simple trial factor program for Mersennes
p = input("Enter a prime number: ")
mer = 2**int(p)-1
mink = 1
maxk = 10000000
for k in range(mink, maxk+1): #test all k's from mink to maxk
  #candidate factor is in the form 2*k*p+1
  candidate = 2*k*int(p)+1
  #check if the candidate is 1 or 7 (mod 8)
  if candidate%8 == 1 or candidate%8 == 7:
    #divide the mersenne number by the candidate and see if it factors it
    if mer%candidate == 0: #the candidate divides the mersenne
      print("M" + str(p) + " has a factor: " + str(candidate))
      break
  else: 
    #if not, go to the next k
    continue
This code first requests an exponent from the user. The program then generates the Mersenne number corresponding to that exponent, and then for all k's running from kmin to kmax, it first creates the corresponding candidate factor, tests if it is 1 or 7 mod 8 and if it is, checks if it divides the mersenne. If it does, it prints the factor to the screen and breaks. If not, it continues until it finds a candidate that works, or it reaches the end of the range.
Test on a known factor:
Code:
Enter a prime number: 7112003
M7112003 has a factor: 355600151
corresponding to k = 25 (see https://www.mersenne.ca/exponent/7112003).

(*) We will cover while loops in the next section.
(**) Note I say simple, not fast. If you want speed, I recommend either using prime95/mprime if you have an x86_64 processor, mfactor from the mlucas suite if you have an ARM processor, factor5 for higher Mersenne's, mfaktc/mfakto for GPU's, or mmff, dm or dmdsieve + pfgw/LLR for Double Mersennes.
Dylan14 is offline