# Blog Archives

## Project Euler Problem#7 solution in C++ (Brute Force)

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.

What is the 10 001st prime number?

Brute Force Solution:

#include <iostream>

using namespace std;

int find_prime (long *numArray, int maxNum)

{

long factor = 2; // we will make 2 as the starting point.

numArray[1] = 0; // rule out 1 from our logic to avoid incorrect results.

// loop condition will check, if we are in our maximum number limit.

//maxNum is the number till there we can find the prime numbers.

while ((factor * factor) < maxNum)

{

for (int i = 2; i < maxNum; i++) // we start our itration from number 2 not from 0 or 1 to get correct results.

{

if (numArray[i] != 0) //if a number on current array index is not zero, it is a prime or we havne’t yet checked it.

{

// we are putting zeros on all multiples of prime numbers, one by one.

if (numArray[i] != factor && (numArray[i]% factor) == 0)

{

numArray[i] = 0;

}

}

}

++factor;

}// after the loop, array will have zeros on all non prime locations and prime numbers.

}

int main ()

{

int prime_count = 0;

int nth_prime = 0;

int maxNum = 0;

int i = 0;

cout << “enter max number for array: “; // you need to test some upper limit values.

cin >> maxNum;

cout << endl << “enter nth prime number you are searching for: “;

cin >> nth_prime;

long *myArray = new long [maxNum];

//we fill up the array till the number we want to find the smallest positive number that is evenly divisible.

for (int i = 0; i < maxNum; i++)

{

myArray[i]= i;

}

// we will get prime numbers till the maxNum by calling below funtions.

find_prime(myArray, maxNum);

for (; i < maxNum; i++)

{

if (myArray[i] != 0)

{

prime_count++;

}

if (prime_count == nth_prime){break;}

}

cout << “the nth prime number is: ” << “value of prime count is: “<< prime_count << ” – ” << myArray[i] << endl;

}

###### Related articles

- Project Euler Problem# 5 solution in C++ (alikhuram.wordpress.com)
- University professor discovers largest prime number to date (phys.org)