C++ 배열에서 소수 개수 세는 방법 (예제 코드 포함)

문제 개요

숫자로 이루어진 배열이 주어졌을 때, 해당 배열 안에 포함된 소수(Prime Number)의 개수를 구하는 것이 목표입니다.

소수란 1과 자기 자신으로만 나누어 떨어지는 수, 즉 약수가 정확히 두 개뿐인 자연수를 말합니다. 따라서 배열의 첫 번째 요소부터 마지막 요소까지 차례대로 각 숫자가 소수인지 검사하고, 소수를 발견할 때마다 카운트를 1씩 증가시키면 됩니다.

소수 판별 원리

숫자 N이 소수인지 확인하려면 2부터 N/2까지 범위의 수 중에서 N을 나누어 떨어지게 하는 수가 존재하는지 검사합니다. 나누어 떨어지는 수가 하나라도 있다면 N은 소수가 아니며, 끝까지 없다면 N은 소수입니다.

입출력 예시

입력 − arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 }

출력 − 소수 개수 : 4

설명 − 2, 3, 5, 7은 소수이고, 1, 4, 6, 8, 9는 소수가 아닙니다.

입력 − arr[] = { 11, 12, 4, 61, 23 }

출력 − 소수 개수 : 3

설명 − 11, 61, 23은 소수이고, 12, 4는 소수가 아닙니다.

알고리즘 접근 방법

임의의 숫자를 담고 있는 정수 배열 arr[]를 준비합니다.
checkPrime(int num) 함수는 전달받은 숫자 num이 소수인지 판별하여, 소수이면 1을 아니면 0을 반환합니다.
num이 1 이하이면 소수가 아니므로 0을 반환합니다.
2부터 num/2까지 반복하면서 num을 나누어 떨어지게 하는 수(num % i == 0)가 있으면 소수가 아니므로 0을 반환합니다.
반복문이 끝날 때까지 나누어 떨어지는 수가 없다면 1을 반환합니다.
변수 isprime은 현재 숫자가 소수인지 여부를 저장합니다(1이면 소수).
변수 count는 배열 arr[]에서 발견한 소수의 개수를 저장합니다.
main 함수에서 배열 전체를 순회하며 각 요소 arr[i]를 checkPrime()에 전달하고, 결과가 1이면 count를 증가시킵니다.
최종적으로 count가 배열 arr[]에 포함된 소수의 개수입니다.

C++ 코드 예제

#include <bits/stdc++.h>
using namespace std;

// 숫자가 소수인지 판별하는 함수
int checkPrime(int num){
    // 1 이하의 수는 소수가 아님
    if (num <= 1)
        return 0;
    // 2부터 num/2까지 나누어 떨어지는 수가 있는지 검사
    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;
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 출력이 생성됩니다 −

배열에 포함된 소수의 개수 : 4

성능 개선 팁

소수 여부는 2부터 √N까지만 검사해도 정확히 판별할 수 있습니다. N/2 대신 제곱근까지만 확인하면 시간 복잡도가 O(N)에서 O(√N)으로 크게 줄어들어, 배열의 크기가 클수록 실행 속도가 눈에 띄게 빨라집니다.