문제

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

풀이

  • 에로타스테네스의 체를 이용해서 소수를 찾으면 된다.
    • 120까지의 모든 소수를 구한다고 해보자. 2부터 120까지 배열에 모두 넣은 후 소수가 아닌 것들을 모두 체크해버리는 것이다.
    • 2를 제외한 모든 2의 배수를 체크한다.
    • 3을 제외한 모든 3의 배수를 체크한다.
    • 4는 2의 배수에서 체크 되므로 소수 아님.
    • 체크가 안된 수들이 소수이다.

코드

시간초과 코드

#include <string>
#include <vector>
using namespace std;

int solution(int n) {
    int answer = 0;

    for(int i = 2; i <= n; i++) {

        int count = 0;

        for(int j = 2; j*j <= i; j++) {
            if(i % j == 0) {
                count++;
            }
        }
        if(count == 0) answer++;
    }
    return answer;
}

에라토스테네스의 체

#include <string>
#include <vector>
using namespace std;
int numbers[1000000] ;
int solution(int n) {

    int answer = 0;


    for(int i = 2; i <= n; i++) {
        if(numbers[i] == 1) continue;
        for(int j = i*2; j <= n; j+=i) {

            numbers[j] = 1;

        }
    }

    for(int i = 2; i <= n; i++) {
        if(numbers[i] == 0) answer++;
    }

    return answer;
}