[Lv.1] 소수 찾기

📝 문제

소수 찾기

💡 생각

처음에 단순하게 이중 for문으로
첫번째 for문 - i:2~n
두번째 for문 - j:2~i
으로 돌리니까 시간초과가 돼서
제곱근 전까지 범위설정, 짝수 배제, 끝자리 5인 수 배제 등... 으로 시도했지만 효율성 테스트에서 한두개정도가 통과가 안됐다

결국 통과된 방법은

1) 소수를 넣을 벡터 생성
2) n>=3이면, 벡터에 3을 넣고(짝수를 배제할 것이므로 2는 넣지 않음)
3) for문을 돌며 소수 벡터 안의 원소로 나누어 떨어지는지 검사
4) 나누어 떨어지면 break
5) 벡터 안의 원소가 제곱근보다 크면 소수이므로 소수벡터에 넣고 break

💻 코드

#include <string>
#include <vector>
#include <cmath>

using namespace std;

int solution(int n) {
    vector<int> v;	// 소수를 넣을 벡터
    if(n>=3) v.push_back(3);
    
    for(int i=5; i<=n; i=i+2){	// 3보다 크며 가장 작은 소수인 5부터, i에 2씩 더해주며 짝수 배제
        for(int j=0; j<v.size(); j++){
            if(i%v[j]==0) break;	// 소수로 나누어 떨어지면 소수가 아님
            if(v[j]>sqrt(i)){	// 제곱근보다 작거나 같은 수로 나누어 떨어지지 않는다면 소수이다
                v.push_back(i);
                break;
            }  
        }
    }
    
    return v.size()+1;	// 소수 벡터에 넣지 않은 2를 더해줌
}

여튼 위의 코드로 테스트 통과했긴 했는데.. 더 효율적인 풀이가 있었다.
에라토스테네스의 체를 이용해서 소수들의 배수를 지워나가는 방법!

#include <string>
#include <vector>

using namespace std;

int solution(int n) {
    int answer = 0;
    vector<bool> tmp(n+1, true);

    for (int i=2; i<n+1; i++) {
        if (tmp[i] == true) {
            answer++;
            for (int j=2; i*j<=n; j++) 
                tmp[i*j] = false;	// 소수 i의 배수들을 모두 false로 바꿔줌
        }
    }

    return answer;
}

나는 모든 수를 돌면서 그 중 소수로 나눠떨어지지 않는 것을 고르려 했다면(for안의 if),
위의 코드는 미리 소수로 나눠떨어질 것들을 배제하고 for문을 돌기 때문에 훨씬 효율적인 것을 볼 수 있다.(if안의 for)
오늘도 생각의 힘을 키워야 겠다고 느낌,,,

내 풀이와 더 효율적인 풀이 실행 결과! 속도차가 많이 나는 걸 볼 수 있다.