🖊️ 문제

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

---

🖊️ 풀이

무지성으로 루프돌면서 풀어버리면?

#include <string>
#include <vector>

using namespace std;

bool isSosu(int n) {
    for (int i = 2 ; i < n ; i++) {
        if (n % i == 0) return false;
    }
    return true;
}

int solution(int n) {
    int answer = 0;
    
    for (int i = 2 ; i <= n ; i++) {
        if (isSosu(i)) answer += 1;
    }
    
    return answer;
}

처참한 엔딩.

당연함
O(N^2) 수준의 미천한 코드니까..

제한조건을 보고도 이따구로 짠거니
부디 점심을 좀 차리시기 바랍니다.......

이대로는 풀 수 없겠다..

수학 관련 문제이니 여러모로 고민해봤지만..
결국 생각이 안나서 구글신에게 도움을 요청했다.

에라토스테네스의 체

ㅋㅋ
이름 외우기도 힘들겠지만.. 소수 구하는 방법이다.

1. 2부터 n까지 모든 자연수을 나열한다
   

2. 2를 제외한 2의 배수들을 제거한다
   

3. 2를 제외하고 남은 자연수들 중 가장 작은 수를 제외하고 그 수의 배수들을 제거한다.
   

4. 제외한거 빼고 남은 자연수 중 가장 작은 수가 n이 될 때까지 3의 과정을 반복
   

끝!

이제 남은 자연수들의 개수를 구하면 소수의 개수이다.

쉽쥬?
이렇게 하면
한 번만 순회하면 되니까 O(N)
쉬우니까 잊지말자!

이대로 하면 된다!

루프 돌면서 가장 작은 자연수 나오면 걔 크기 만큼씩 더해주면서 아니라고 바꿔주다보면 됨
알고리즘을 몰랐다~

---

🖊️ 코드

#include <string>
#include <vector>

using namespace std;

int solution(int n) {
    int answer = 0;
    
    vector<bool> num(n+1, true);
    
    for (int i = 2 ; i <= n ; i++) {
        if (num[i] == false) continue;
        
        for (int j = i * 2 ; j <= n ; j += i) {
            num[j] = false;
        }
    }
    
    for (int i = 2 ; i <= n ; i++) {
        if (num[i]) answer += 1;
    }
    
    return answer;
}

---

참고한 자료

https://velog.io/@changhee09/알고리즘-소수의-판별-에라토스테네스의-체