(C++) - 프로그래머스(연습문제) : 소수찾기

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

코딩테스트 연습 - 소수 찾기

아리스토텔레스의 체를 이용해 소수를 찾는 문제였습니다.

 

풀이방법

 1. 100만까지의 소수 아닌 것을 체크해줍니다.

 2. 2부터 n까지 중 체크가 안되어 있는 것은 소수이므로 답을 더해줍니다.

Code

#include <bits/stdc++.h>
using namespace std;

void primeInit(int ck[]){
    for(int i = 2 ; i <= 1000000; i++){
        if(ck[i]) continue;
        for(int j = i+i; j <= 1000000; j+=i){
            ck[j] = 1;
        }
    }
}

int solution(int n) {
    int answer = 0;
    int ck[1000001];
    memset(ck,0,sizeof(ck));
    primeInit(ck);
    for(int i= 2; i <= n; i++) if(!ck[i]) answer++;
    return answer;
}