[백준/c++] 1978번 소수 찾기

1978번 문제 링크

문제

주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오.

입력

첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다.

출력

주어진 수들 중 소수의 개수를 출력한다.

풀이

소수는 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수로 구하는 방법엔 여러가지가 있는데 이번엔 1️⃣ 에라토스테네스의 체 와 2️⃣ 제곱근까지 나누어 떨어지는지 확인 하는 방법을 사용하려고 합니다.

1️⃣ 에라토스테네스의 체 는 간단하게 소수를 구해야 하는 범위의 제곱근 보다 작은 소수의 배수를 지우고 남은 수는 모두 소수 라는 공식을 사용하는 방식이고,

2️⃣ 제곱근까지 나누어 떨어지는지 확인 하는 방법 은 2 ~ 제곱근까지 반복문을 돌면서 나누어 떨어지는 수가 있으면 소수가 아니라고 판단하는 방식입니다.

자세한 건 해당 포스팅을 참고해주세요. 👉 [알고리즘] 소수 (Prime Number)

소스코드

1. 에라토스테네스의 체 사용

#include <stdio.h>
#include <iostream>

using namespace std;

int main() {
    
    int n; 		// 숫자의 개수 
    cin >> n;
    
    int num_arr[n];		// 입력 받은 숫자를 저장하는 배열 
    int max_num = 0;	// 입력 받은 수 중 가장 큰 수 
    
    for(int i=0; i<n; i++) {
        cin >> num_arr[i];
        if (max_num < num_arr[i]) max_num = num_arr[i];
    }
    
    // max_num 까지 소수의 여부를 구하기 떄문에 
    //소수 여부를 저장하는 배열 크기를 max_num + 1 로 잡아준다
    bool is_prime_num[max_num+1]; 
    for(int i=0; i<max_num+1; i++) is_prime_num[i] = true; // 배열 true 로 초기화 
    
    is_prime_num[1] = false; // 1은 소수가 아니기 때문에 false
        
    // 에라토스테네스의 체 방식으로 가장 큰 값의 제곱근까지 반복문을 돌리고
    for (int i=2; i*i<=max_num; i++) {
    	// 해당 값의 배수인 값은 배열에 소수로 저장해준다.
        for(int j = i+i; j<=max_num; j+=i) {
            is_prime_num[j] = false;
        }
    }
    
    int prime_count = 0;
    // 숫자의 개수까지 반복문을 돌면서 
    // 소수인지 아닌지 여부를 판단하고 소수 인경우 prime_count 에 ++
    for(int i=0;i<n;i++) {
        if (is_prime_num[num_arr[i]]){
            prime_count++;
        }
    }
    
    cout << prime_count;
    
    return 0;
}

2. 제곱근 사용

#include <stdio.h>
#include <iostream>

using namespace std;

int main() {
    
    // N = 숫자의 개수 
    // num = 입력받은 숫자 
    // is_not_prime_num_cnt = 소수가 아닌 합성수의 개수
    int N, num, is_not_prime_num_cnt = 0;
    cin >> N;
    
    for(int i=0;i<N;i++) {
        cin >> num;
        
        if (num == 1) {
        	// 1 은 소수가 아니기 때문에 ++
            is_not_prime_num_cnt++;
        } else {
        	// 입력 받은 값의 제곱근까지 돌면서 
            // 소수인지 아닌지를 판단 
            for(int i=2; i*i <= num; i++) {
                if (num % i == 0) {
                    is_not_prime_num_cnt ++;
                    break;
                }
            }
        }
    }
    
    cout << (N-is_not_prime_num_cnt);
    return 0;
}

처음에는 여러 값을 입력 받으니깐 에라토스테네스의 체를 사용하면 간단하게 풀 수 있을 것 같다 라고 생각해서 에라토스테네스의 체를 먼저 사용했었는데 배열을 효율적으로 사용하려고 하다보니깐 생각보다 코드가 길어지고 반복문이 많아졌습니다. 🥲

메모리가 동일한 상황에선 코드 길이가 짧고 가독성이 좋은 2️⃣ 제곱근 사용 이 조금 더 좋은 방식인 것 같습니다.

정답