Write-Up/Algorithm

프로그래머스 - 소수의 합

NONE_31D 2019. 3. 23. 15:41

C++

#include <iostream> #include <vector> #include <cmath> using namespace std; long long solution(int N) { long long answer = 0; vector<long long> v; for (int i = 0; i <= N; i++) { v.push_back(i); } int i, j; for (i = 2; i <= N; i++) { if (v[i] == 0) continue; else { for (j = i * 2; j <= N; j += i) { v[j] = 0; } } } v[1] = 0; for (int i = 2; i <= N; i++) { if (v[i] != 0) answer += v[i]; } return answer; }

일반적으로 알고리즘 책이나 풀이로는 2를 배열에 넣어두고, N까지 반복문을 두며 배열 안에 있는 수로 나누어 떨어지면 소수가 아니고, 끝까지 나누어떨어지지 않으면 소수라고 정하는 풀이가 많이 나왔었다.

//의사코드 arr = {2} //소수가 들어갈 배열 for(i=2;i<N;i++){ for(j=0;j<arr.size();j++){ if(i%arr[j]==0) break; arr.push_back(i); } }

위와 같은 코드는 맨 위에 솔루션으로 올린 코드보다 복잡도가 큰데, 이건 미리 알아볼 예정.

솔루션의 코드는

for (i = 2; i <= N; i++) { if (v[i] == 0) continue; else { for (j = i * 2; j <= N; j += i) { v[j] = 0; } } }

이렇게 실제로 체를 쳐내는 듯한 과정을 구현해낸다.

(이미지출처 : 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)

위에 올린 gif를 보며 코드를 이해하면 쉬울 것 같음 'w'


'Write-Up > Algorithm' 카테고리의 다른 글

프로그래머스 - 완주하지 못한 선수  (0) 2019.03.23
프로그래머스 - 모의고사  (0) 2019.03.23
프로그래머스 - 스킬트리  (0) 2019.03.23
프로그래머스 - K번째 수  (0) 2019.03.23