1. 작성 이유

https://school.programmers.co.kr/learn/courses/30/lessons/12921

프로그래머스 코테 문제풀다 소수 찾기 문제를 푸는데 구현 다 했는데 시간걸리는게 심상치 않아서 보니까

시간이 아주 그냥 하늘을 뚫어버리는 정도였다.

당시 문제의 소스

#include <string>
#include <vector>

using namespace std;

int solution(int n) {
    int answer = 0;
    for (int i = 2; i <= n; i++) {
        answer++; //소수라고 가정
        for (int j = 2; j < i; j++) {
            if (i % j == 0) { //소수가 아니면?
                answer--; 
                break;
            }
        }
    }
    return answer;
}

당연히 2중 for문 돌리고 있으니까 시간복잡도가 O(n^2)가 나올 수밖에 없는 코드긴 한데...
그럼 소수를 엄청 간단하게 구하는 방법이 뭐가 있을까?

https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

2. 에라토스테네스는 신이고 무적이다

에라토스테네스가 발견한 소수 찾기 방법이다.

방법은
1. 1을 제외한 모든 수를 소수로 보고 시작한다.(소수를 i로 본다고 가정)
2. 만약 i를 소수로 판별했을 때, i 의 i 배수부턴 모두 소수가 아닌 수로 판별.

#include <string>
#include <vector>

using namespace std;

int solution(int n) {
    int answer = 0;
    bool* arr = new bool[n + 1];
    //소수를 담을 공간. 2부터 시작해 입력받은 n값을 담음

    for (int i = 2; i <= n; i++) {
        arr[i] = true;
    } // 2부터 모두 소수로 보고 시작함.

    for (int i = 2; i*i <= n; i++) {
        if (arr[i]) { //만약 이 숫자가 소수면?
            for (int j = i + i; j <= n; j += i) arr[j] = false;
        } // 그 다음 배수부턴 다 소수가 아닌 것
    }
    for (int i = 2; i <= n; i++) {
        if (arr[i]) answer++;
    }
    return answer;
}

시간복잡도는 O(n log(logn))

사실 별거 아닌것 같은 내용인데 포스팅한 이유는
1년 전에 파이썬으로 백준에서 똑같은 문제를 풀었지만 까먹은 나 자신이 바보같아서 썼다...