NIGHT_TYPE

Mike Garcia

until your eyes bleed

17. September 2014 782 words ~4 minutes read Comment

Using Nested for Loops in C++ to Find Prime Numbers

A prime number (or a prime) is a natural number greater than 1 that has no positive divisors other than 1 and itself.

Wikipedia

It comes up quite a bit that you will need to run a loop inside of another loop. For these examples we are trying to find prime numbers between 3 and 100.

In the 2nd part of this post, I’ll then encapsulate part of the program into a separate function we can call to ask if a number is prime or not.

How To:

We’re gonna need 1 loop to generate a number (n) to test if it’s prime (only divisible by itself & 1).

And then a second loop to divide the potential prime number (n) by every number between 1 and that number divide by 2 (n/2).

Note that the biggest factor we need to test for is (possible prime divided by 2), because every number we test after that would result with a remainder or “1” (which it’ll obviously divide by).

 

There’s plenty of ways you could do this, this was my pretty direct/simple way, I’ve tried to make comments on the code to explain what I’m doing.

/******************************************************************************
Title: lab03b.cpp
Author: Mike Garcia
Created on: 9/16/2014
Description: Outputs all primes between 3 & 100
Usage: ./lab03b
Build with: g++ lab03b.cpp -o lab03b
Dependencies: NONE
******************************************************************************/
#include <iostream>
#include <iomanip>
using namespace std;

int main(){
    // 1st loop is the # we're checking to see if prime
    for (int i = 3; i < 1000; i++){
        // initialized bool that will be tripped if # is divisible
        bool isPrime = true;

        // increase and retest every divisor up to proposedPrime/2 (since we know that's the largest divisible factor)
        for (int j = 2; j < i/2 ; j++){
            // if our possiblePrime is divisible, then it's not prime & we trip the isPrime bool
            if (i%j==0){
                isPrime = false;
            }
        }

        // after we've ran through all the divisors for this possiblePrime, we check if the bool was tripped
        if (isPrime){
            // if NOT tripped, then possiblePrime is in fact Prime!
            cout << setw(3) << i << " is a prime #" << endl;
        }
    }
return 0;
}

 

Now for the second part, we’ll want to put the prime checking loop into it’s own function so we can improve the readability  of our code. Also this will make it easy to reuse in other projects if need be.

Basically we just took everything inside the 1st for loop from above and put it in it’s own bool function. This way, when you call isPrime(your#) it will send your number you want to check and return True or False.

Here’s what the code looks like:

/******************************************************************************
Title: lab03c.cpp
Author: Mike Garcia
Created on: 9/16/2014
Description: checks if # is prime, primeChecker is separate function
Usage: ./lab03c
Build with: g++ lab03c.cpp -o lab03c
Dependencies: NONE
******************************************************************************/
#include <iostream>
using namespace std;

bool isPrime (int n);
//Precondition: pass an int to check if prime
//Postcondition: return true if # was prime, or false if not.

int main(){
    // 1st loop is the # we're checking to see if prime
    for (int i = 3; i < 101; ++i){
        if (isPrime(i)){
            cout << i << " is a Prime Number" << endl;
        }
    }
return 0;
}

// test if possible prime is divisible by 2 to n/2
bool isPrime (int n){
    bool testPrime= true;
    for (int j = 2; j < n/2; ++j){
        if (n % j == 0){
            testPrime = false;
        }
    }
    // if divisor found, set bool to false, otherwise will return true
    return (testPrime);
}

Good Luck!

Leave a Reply