[프로그래머스/lv1] 소수 찾기 - 에라토스테네스의 체 (vector)

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

프로그래머스

 

참고자료

https://school.programmers.co.kr/questions/21359

프로그래머스

개천재

기존 코드 - 틀린 코드

에라토스테네스의 체를 썼다.

처음에는 정확성은 통과하는데 효율성은 전부 시간초과였다.

#include <vector>
#include <cmath>

using namespace std;

int era[1000001]{};
// -1 : 소수 아님
// 0 : 미방문
// 1 : 소수
int eratos(int N){
    int cnt = 0;
    era[0] = -1;
    era[1] = -1;
    
    for(int n = 2; n <= N; n++){
        if(era[n] != 0) continue; // 이미 방문한 곳은 패스
        bool isPrime = true; // 소수 판별 변수
        
        // 소수 판별. 나누기는 루트n까지만 돌면 충분
        for(int j = 2; j <= sqrt(n); j++){
            if(n % j == 0){ // 나누어 떨어지는게 하나라도 있으면 소수 아님
                isPrime = false; // 소수 아님
                break;
            }
        }
        if(isPrime) {
            era[n] = 1;
            cnt++;
        }
        else era[n] = -1;
    }
    return cnt;
}

int solution(int N) {
    int answer = 0;
    answer = eratos(N);
    return answer;
}

 

기존 코드 - 정답 코드

그랬다가 [질문하기]에서 모든 합성수는 소수의 곱으로 이루어져있다는 글을 보고 충격.

소인수분해가 그거였지!

그래서 소수 판별 반복문에서 나누는 수를 소수인 수로만 나누도록 딱 한 줄 추가했다.

        // 소수 판별. 나누기는 루트n까지만 돌면 충분
        for(int j = 2; j <= sqrt(n); j++){
            if(era[j] != 1) continue; // 모든 합성수는 소수의 배수이므로 소수인걸로만 나누기
            if(n % j == 0){ // 합성수 = 소수로 나눴을 때 나누어짐
                isPrime = false; // 소수 아님
                break;
            }
        }

 

문제점

하지만 이미 시간복잡도는 이미 루트n 만큼 발생 중이라 더 줄이는 방법을 모색했다.

루트n까지의 모든 수를 탐색할 필요가 있을까?

 

굳이 배열 era[겁나큰숫자]에 모든 수들이 합성수인지 소수인지 둘다 아닌지를 판단할 필요가 있을까로 귀결.

 

합성수 = 소수의 곱

이므로 소수만 담은 vector를 만들면 되지 않을까?

그리고 소수 개수도 vector의 size만 return하면 되지!

라는 생각이 들었다.

 

정답 코드 : 소수만 담은 vector

훨씬 더 간결해졌다.

#include <vector>
#include <cmath>

using namespace std;

int eratos(int N){
    vector<int> prime; // 소수만 담기
    for(int n = 2; n <= N; n++){
        bool isPrime = true;
        for(int p : prime){ // 소수만 확인
            if(n % p == 0){ // 합성수 = 소수의 곱
                isPrime = false;
                break;
            }
            if(p > sqrt(n)) break; // 소수가 루트n를 벗어나면 반복 종료
        }
        if(isPrime) prime.push_back(n); // 소수라면 prime에 보관
    }
    return prime.size(); // 소수 개수를 return
}

int solution(int N) {
    int answer = 0;
    answer = eratos(N);
    return answer;
}