[프로그래머스] 알고리즘 72일차 : 소수 찾기

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

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

C++ 소수 <에라토스테네스의 체>

프로그래머스 코데 연습 문제 level 1

정해진 범위 내에서 소수 개수 찾는 문제인데 단순하게 풀면 시간초과 나서

에라토스테네스의 채로 풀어야 하는 문제

평소에 잘 안쓰는 함수를 써봤다.

 

오답노트

에라토스테네스 체로 제출했는데도 효율성검사에서 걸렸었는데

틀린 부분은 가장 바깥 반복문 돌때 어차피 배수를 지워나가는거라 반 이상은 돌 필요 없는걸 간과해서

일단 그 부분 고쳤고

그 다음엔 배열상 소수라고 되어있는 것은 아직 확인이 안된거라 다시 소수인지 확인해봐야 한다고 생각했는데

사실 2부터 시작해서 소수의 배수를 지워가는 거라면 당연히 소수가 아니라고 체크되지 않은 수는 소수이기 때문에

그 부분도 지워서 제출하고 통과 (에라토스테네스의 체로 이전에 풀었던 코드가 있어서 내껄 내가 참고함..)

 

소스코드

#include <string>
#include <vector>

using namespace std;

bool isPrime[1000001];
void updateIsPrime(int n,int end){
    for(int i = n*2 ; i <= end ; i += n){
        isPrime[i] = false;
    }
}
int solution(int n) {
    int answer = 0;
    for(int i = 2 ; i <= n ; i++ ){
        isPrime[i] = true;
    }
    for(int i = 2 ; i <= n/2 ; i++){
        if(!isPrime[i]){
            continue;
        }else{
            updateIsPrime(i,n);
        }
    }
    for(int i = 2 ; i <= n ; i++){
        if(isPrime[i]){
            answer++;
        }
    }
    return answer;
}