# 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.

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!