프로그래머스 - 소수 찾기 C++

소수 찾기! 일단 소수란 1과 자기 자신으로만 나눠지는 수를 의미하며, 1은 소수가 아니다.

 

그럼 for문을 돌려서 하나씩 구해주자니 n이 너무 큰 숫자다.. 그래서 n이 큰걸로 보이는 테스트케이스는 시간 초과가 났었음

 

그래서 에라토스테네스의 체를 이용해보자. 잘 모르겠으면 

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

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전

여기 친절하게 설명되어있다.

 

일단 이걸 보고 푼게 아래 코드. 모든 숫자가 소수라는 가정 하에 true로 초기화시켜준다.

이제 계산하면서 중복계산만 안하게끔 해주면 되는데

arr[i]가 true라는 것은 i는 소수이며, i의 배수들은 소수가 아니라는 뜻이므로 배수들을 false로 바꾸어준다.

            for(int j=i*i; j<=n;j+=i)

여기서 j의 초기값은 i*k (k < i) 까지는 이미 검사되었으니까 j = i*2가 아니라 i*i로 개선시켜준다.

#include <string>
#include <vector>
#include <iostream>
using namespace std;
 
int solution(int n) {
    int answer = 0;
    vector <bool> arr(n+1,true);
 
    
    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;
}

이 코드는 다른 사람이 푼 방법인데, 정확도와 효율성 모두 만점이지만 위의 코드보다는 효율성이 좀 떨어진다.

중복계산처리를 안해줬으니까 당연한,,

#include <string>
#include <vector>
#include <iostream>
using namespace std;
 
int solution(int n) {
    int answer = 0;
    vector <bool> arr(n+1,true);
        
    for(int i=2;i<n+1;i++){
        if(arr[i]){
            for(int j=2; i*j<n+1;j++)
                arr[i*j]=false;
            answer++;
        }
    }
    
    return answer;
}