[백준 알고리즘/ C++] BOJ.1978 : 소수 찾기

문제

https://www.acmicpc.net/problem/1978

1978번: 소수 찾기

 

---

풀이

자료구조

- int num : 입력 수

- int input[] : 입력

- int arr[1001] : 에라스토테네스 체에 쓸 배열

- int count : 소수 개수 카운트

 

알고리즘

- 에라스토테네스의 체 사용해서 소수 구하기

 

코드

- C++의 <cmath> 라이브러리에서  sqrt()함수를 사용하면 제곱근을 쉽게 구할 수 있다

---

코드 

#include <iostream>
#include <cmath>
using namespace std;

int main() {

    //입출력 최적화
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int num = 0;
    int input[100];
    int arr[1001] = {0};
    int count = 0;
    arr[0] = 1, arr[1] = 1;  //0이랑 1 예외처리

    cin >> num;  //입력
    for(int i = 0; i < num; i++) {
        cin >> input[i];
    }

    //에라스토테네스의 체
    for(int i = 2; i <= (int)sqrt(1000); i++) {
        if(arr[i] == 0 ) {
            for(int j = 2; j <= (int)(1000 / i); j++) {
                 arr[i*j] = 1;
            }
        }
    }

    for(int i = 0; i < num; i++) {
        if(arr[input[i]] == 0) {
            count++;
        }
    }

    cout << count << "\n";
    return 0;
}

 

---

총평

나는 제곱근을 사용하는 개선된 에라스토테네스의 체를 사용해서 풀었다.

다른 사람들 코드를 보니 입력값의 숫자가 소수인지 판별해서 푸는 풀이법도 많이 보였다.

그러나 입력값이

3

983 991 997

이렇게 주어지면 계산이 너무 많아질 거 라고 생각했다.

오랜만에 에라스토테네스의 체를 구현해서 재밌었던 문제다.