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[]