Need help with algorithim for finding and printing prime numbers in an arra

[Celestic]

The issue I'm having is I am having trouble writing the code to find prime numbers in an array. The assignment requires us to open a data file and then our program computes the data file and outputs a bunch of stuff such as average,variance,deviation,prime numbers, etc on an output file. Right now I've completed everything except finding prime numbers from the data file when it is entered into the array. Below is the code that I've tried so far.

void prime(ofstream& outfile, int list[], int n)
{
  int i;
  int count = 0;
  for(i = 0; i < n; i++)
    {
      if(list[i] % (i+1) == 0)
        count++;
      cout << list[i] << " " << count << endl;; //this line is just for me to see if the prime numbers are getting the same counter or not.
    }
  if(count == 2)
    {
      cout << list[i] << endl;
    }
}

[TheIdeasMan]

http://www.cplusplus.com/forum/general/179865/

Duplicate post. Please don't do this, it is ultimately a time waster. Go to the other Topic and delete it before some one replies to it. If they have, direct them to answer this Topic.

You need a nested loop: the outer one to process the array, the inner one to do all the numbers up to the number in question, with a limit of sqrt(n).

This is the typical naive approach and is very inefficient, ok for a small limit though. The problem is when a number is prime, all the numbers before it are checked. When another prime is encountered (which may only be a small amount higher than the previous one) all those numbers are checked again.

A better approach is to remove multiples of prime numbers form a list, as in multiples of 2,3,5,7 etcetera. The next multiple to check for is the next number in the list. So remove multiples of 2, then 3, then the next is 5 because 4 is gone already. An improvement is to start from the square of the number. So if you are doing multiples of 5, start at 25 because all the numbers up to there are already prime.

Good Luck !!

[Celestic]

How do I do the inner loop? I am really bad at nested looping.

[Celestic]

This is what I came up with but it still doesn't work

void prime(ofstream& outfile, int list[], int n)
{
  int i;
  int count = 0;
  for(i = 0; i < n; i++)
    {
      for(int j = 2; j < sqrt(n); j++)
        {
          if(list[i] % j == 0)
            count++;
        }
      cout << list[i] << " " << count << endl;
    }
}

[Thomas1965]

If you would write a function IsPrimeNumber can you don't need an inner loop.

bool IsPrimeNumber(int num);

void prime(ofstream& outfile, int list[], int n)
{
  int i;
  int count = 0;
  for(i = 0; i < n; i++)
  {
    if (IsPrimeNumber(list[i]))
    {
      count++;
      cout << list[i] << " " << count << endl;
    }
  }
}

[48T7M4Gy]

This is another good source and effective pseudocode
https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes