C++program to count prime numbers in an array

Write a C++ program to count prime numbers in an array

In this blog, we will create a program to count prime numbers in an array using C++.

What are Prime numbers?

Numbers have only two factors i.e. 1 and the number itself known as Prime numbers.

Example: 2,3,5,7,11,13…etc.

Algorithm to count prime numbers

Naive approach: A simple solution is to loop through the array and constantly check each element to see if it is prime or not while maintaining the number of prime elements.

Efficient approach: Generate all prime numbers up to the maximum number of array elements using the Sieve of Eratosthenes and store them in a hash. Now loop through the array and use the hash table to find the number of those elements that are prime numbers.
Below is an implementation of the above approach:

C++ program to count prime numbers in an array

#include <bits/stdc++.h>
using namespace std;
// Function to find if number is prime
int checkPrime(int num){
if (num <= 1)
{ return 0; }
// Check from 2 to half of arr[i]
for (int j = 2; j <= num/2; j++){
if (num % j == 0){
return 0;
}
return 1;
}
}
int main(){
int arr[] = { 1,3,5,4,8,13,11 };
int n = 7;
int count=0;
int isprime=0;
for(int i=0;i<n;i++){
isprime=checkPrime(arr[i]);
if(isprime==1)
count++;
}
cout<<"Count of number of primes in array : "<<count;
return 0;
}

Explanation of the code

  • We take an integer array arr[] containing random numbers.
  • The check Prime(int num) function checks whether the passed number num is prime or not. Returns 1 if prime, otherwise returns 0.
  • If number <=1 then not prime, returns 0.
  • Now start from 2 to num/2 if any number fully divides num ( num%i==0) then num is not prime then return 0.
  • Otherwise, return 1.
  • The variable is prime tells whether the number is prime or not (1 means prime)
  • Variable count stores the number of primes in arr[]
  • Inside main, loop through the entire array and pass each element to arr[i] checkPrime( arr[i] ), if the result is 1 ( isprime==1 ), then increment the count.
  • At the end of the count is the number of primes in arr[]

Output