1

I'm trying to write a function that finds the number of prime numbers in an array.

int countPrimes(int a[], int size)
{
    int numberPrime = 0;
    int i = 0;
    for (int j = 2; j < a[i]; j++)
    {
        if(a[i] % j == 0)
            numbPrime++;
    }
    return numPrime;
}

I think what I'm missing is I have to redefine i after every iteration, but I'm not sure how.

Dan
  • 21
  • 1
  • 1
  • 3
  • 4
    For one thing, `numberPrime`, `numbPrime` and `numPrime` are not the same variable. – Tripp Kinetics Jul 31 '15 at 21:27
  • 1
    Your logic is incorrect - you will find all numbers that are divisible by some number 0 ... a[i] - that is not prime numbers... And yes, you need a for-loop outside the `for( j = ... )` loop. – Mats Petersson Jul 31 '15 at 21:27

1 Answers1

5

You need 2 loops: 1 over the array, 1 checking all possible divisors. I'd suggest separating out the prime check into a function. Code:

bool primeCheck(int p) {
    if (p<2) return false;

    // Really slow way to check, but works
    for(int d = 2; d<p; ++d) {
        if (0==p%d) return false; // found a divisor
    }
    return true; // no divisors found
}

int countPrimes(const int *a, int size) {
    int numberPrime = 0;
    for (int i = 0; i < size; ++i) {
        // For each element in the input array, check it,
        // and increment the count if it is prime.
        if(primeCheck(a[i]))
            ++numberPrime;
    }
    return numberPrime;
}

You can also use std::count_if like this:

std::count_if(std::begin(input), std::end(input), primeCheck)

See it live here.

BoBTFish
  • 19,167
  • 3
  • 49
  • 76
  • … and if you’re writing a dedicated function anyway, you can also use [`std::count_if`](http://en.cppreference.com/w/cpp/algorithm/count) to simplify your code. – Robin Krahl Jul 31 '15 at 21:32
  • @RobinKrahl Good suggestion, thanks, I will edit it into my answer in a minute. Just started with what (s)he already had. – BoBTFish Jul 31 '15 at 21:35
  • One simple optimization: `for(int d = 2; (d*d)<=p; ++d) { /* ... */ }`. Of course, then there's the chance that `d*d` overflows that needs to be considered... – Michael Burr Jul 31 '15 at 21:38
  • 1
    @MichaelBurr I didn't want to go down that road, it's a whole book at least. Just going for correct. – BoBTFish Jul 31 '15 at 21:42
  • @BoBTFish Thanks! :) For those who are confused by the `size` template in the example code (like I was – `(&)`?!), [here](http://stackoverflow.com/questions/3368883/how-does-this-size-of-array-template-function-work)’s the explanation. – Robin Krahl Jul 31 '15 at 21:48
  • 1
    @RobinKrahl Ah sorry about that. It's a handy little trick that will be in The Standard from 2017, but the syntax is a bit funky. I didn't bother explaining since it's not really part of the question. `std::begin` and `std::end` for arrays work a similar way. – BoBTFish Jul 31 '15 at 21:50
  • optimization? for(int d = 2; d<=p/2; ++d) – RadijatoR Jul 31 '15 at 21:52
  • @RadijatoR The optimization suggested by Michael Burr is better. – BoBTFish Jul 31 '15 at 21:52