The First 50 Primes

[GoranGaming]

Hello!
I was reading a book about C++-programming and encountered a rather difficult exercise, it's in Swedish so I'll have to translate it for you:

"To show that an integer is a prime number you can test if it isn't evenly divisible by smaller prime numbers. Using this piece of knowledge, and arrays or vectors, you're supposed to construct a program that finds the first 50 prime numbers, and prints them out."

(I might have gotten the translation a little bit wrong somewhere, because I'm not very familiar with all of the English mathematical terms.)

I've tried everything, at least it feels like it, but my program either outputs nothing, or crashes. I've no idea how to do this, and when looking at the solutions offered in the book I didn't understand what they were doing or why they were doing it. Could you help me in solving this problem? And if you post code, please give me a brief explanation of what you're doing and why! :) Thanks!

[vlad from moscow]

I think that your task is not to get some code from the forum but understand the solution shown in the book.

[Chervil]

Well, finding prime numbers is a very common exercise. If you use the search box at the top of this page, you should find many examples.

If you need help with your own code, please post it here so someone can look at it to identify the problem(s).

[GoranGaming]

I thought that someone here maybe would be able to explain it better than the book did, it offered no explanation at all. But sure, I'll look into their code a little bit more.

[R10111001]

#include <iostream>

int main()
{
	const int max = 50;
	long primes[max] = {2, 3, 5};
	
	long trial = 5;
	int count = 3;
	bool found = false;

	do
	{
		trial += 2;
		found = 0;

		for(int i = 0; i < count; i++)
		{
			found = (trial % *(primes + i)) == 0;
			if(found)
				break;
		}

		if(!found)
			*(primes + count++) = trial;
	}while (count < max);

	return 0;
}

I can elaborate on any parts that might confuse you.

[GoranGaming]

Sadly, nothing happens when I try to run your program. Maybe it's because you forgot the "using namespace std;" line?

[R10111001]

It's not my code, it's from a book. I left out the code that outputs the results and edited my code because I forgot to initialize the array. You could write the output to the console screen in the following way:

for(int i = 0; i < MAX; i++)
{
	if(i % 5 == 0) 
	cout << endl;
	cout << setw(10) << *(primes + i);
}

Be sure to include <iomanip> though.

[vitalishe]

Goran,
this is a classical problem.
Here is my solution. Hopefully it will be easy to follow.

Essentially, I am progresively making a list of prime numbers which I store in vector called prime.
'i' is the number I am checking to be prime or not.
If it is, I add it to the list of primes.
If it is not I increment it by one (i++) and continue checking.

#include <iostream>
#include <vector>

using namespace std;

int main()
{
   const int N = 50;    // number of primes
   vector<int> prime;
   prime.reserve(N);    // allocate space for N primes

   int i,j,n = 0;
   bool isPrime;

   for(i=2; n<N; i++){
      // Check if i is a prime, i.e.
      // if it is divisible by one of the found primes
      isPrime = true;

      for(j=0; j<n; j++){
         if(i % prime[j] == 0){
            isPrime = false;
            break;
         }
      }

      if(isPrime){
         prime[n]=i; // add to the list of primes
         n++;        // increment the number of found primes
      }
   }

   cout << "The " << N << "-th prime number is " << prime[n-1] << endl;

   return 0;
}

[GoranGaming]

@ R10111001

found = (trial % *(primes + i)) == 0;

Why is there a multiplication sign before (primes + i)?

(primes + i)

And how can you add an array with an int when you have not clarified what part of the array you want to add? Shouldn't it be like this instead:

(primes[some variable] + i)

[Daleth]

"Why is there a multiplication sign..."
That is because it is an indirection operator, not multiplication. primes as an array is a pointer underneath, which R10111001 treats it as. When he adds i, he adds it not to the value in the array but to the pointer to access a different part of the array. you can think of *(primes+i) as primes[i].