[프로그래머스/c++] Lv1 소수 찾기

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

프로그래머스

간단하게 2중 for문으로 구할 수 없는 문제이다. 이유는 시간 초과..효율성이 매우 떨어진다. 

주어진 조건은 n이 1000000 이하기 때문에 n이 굉장히 커진다. 

 

해결할 수 있는 방법은 에라토스테네스의 체를 사용하면 된다. 

#include <string>
#include <vector>

using namespace std;

int solution(int n) {
    int answer = 0;
    
    int arr[1000001];
    
    for(int i=2;i<=n;i++){
        arr[i]=i;
    }
    
    for(int i=2;i<=n;i++){
        if(arr[i]==0)
            continue;
        for(int j=i+i;j<=n;j+=i){
            arr[j]=0;
        }
    }
    for(int i=2;i<=n;i++){
        if(arr[i]!=0)
            answer++;
    }
    return answer;
}

https://hello-world-cpp.tistory.com/25

정리해놨다.