[프로그래머스] level 1 소수의 합

문제

https://programmers.co.kr/learn/courses/30/lessons/14406

코딩테스트 연습 - 소수의 합 | 프로그래머스

 

 

 

 

풀이

1) 처음에 스스로 짰던 시간 초과 코드(C++)

 

#include <iostream>
using namespace std;
 
bool is_prime(int n) {
    bool chk = true;
    for (int i = 2; i < n; i++) {
        if (n%i == 0) {
            chk = false;
            break;
        }
    }
    return chk;
}
 
long long solution(int N) {
    int answer = 0;
    for (int i = 2; i <= N; i++) {
        if (is_prime(i))
            answer+=i;
    }
    return answer;
}

 

이 코드는 정확성 테스트는 모두 통과했지만, 효율성 테스트에서는 모두 실패했습니다.

성능을 향상시키기 위해서 구글 검색을 했고, 에라토스테네스 체라는 개념을 이용하면 훨씬 효율적인 코드를 작성할 수 있는 것을 알게 되었습니다.

 

 

 

 

2) 에라토스테네스 체 방식 코드(C++)

 

 

이 방식은 제일 작은 소수인 2부터 배수를 모두 배제하는 방식입니다.

자기 자신을 제외한 배수들을 차례로 지워가다보면 결과적으로 소수만 남게 되는 방식입니다.

 

#include <vector>
#include <math.h>
using namespace std;
 
long long solution(int N) {
    long long answer = 0;
    vector<int> vec = vector<int>(N+1);
    for (int i = 2; i <= N; i++)
        vec[i] = i;
 
    for (int i = 2; i < sqrt(N+1); i++) {
        for (int j = i + i; j <= N; j += i) {
            vec[j] = 0;
        }
    }
 
    for (int i = 2; i <= N; i++)
        if (vec[i]!=0)
            answer += i;
 
    return answer;
}

 

 

출처

https://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

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