• 문제 설명 : 2부터 N까지의 모든 소수의 합을 구하세요.
    N이 7이라면 {2,3,5,7} = 17을 출력 하시면 됩니다.
    N의 범위는 2이상 10,000,000이하 입니다.
    효율성 테스트의 모든 시간 제한은 1초입니다.
  • 내가 만들어본 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <vector>
#include <math.h>
 
using namespace std;
int count = 0;
 
long long solution(int N) {
    long long answer = 2;
    for(int i=3;i<=N;i++){
        if(i%2 == 1){
            for(int j=2;j<=sqrt(i);j++){
                if(i%j == 0){
                    count ++;
                }
                if(count == 1){
                    break;
                }
            }
            if(count == 0){
            answer+=i;
            }
        }
    count = 0;
    }
    return answer;
}
cs
  • 코드 채점 결과

  • 2019년 3월 25일 수정
  • 소수에 대한 최적의 알고리즘이 있다는 것을 오늘에야 알게 되었다. 그건 바로 에라토스테네스의 체 -> https://marobiana.tistory.com/91
  • 이 알고리즘은 자신을 제외한 배수들은 소수가 아니라는 것을 이용하여 만든 알고리즘이다.
  • 수정한 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <vector>
 
using namespace std;
 
long long solution(int N) {
    long long answer = 0;
    vector<int> all;
    for(int i = 0;i<=N;i++){
        all.push_back(i);
    }
    
    for(int j=2;j<=N;j++){
        if(all[j] == 0){
            continue;
        }
        else{
            for(int z=j+j;z<=N;z+=j){
                all[z] = 0;
            }
        }
    }
    
    for(int a=0;a<=N;a++){
        answer += all[a];
    }
    return answer-1;
}
cs
  1. 먼저 0부터 N까지의 수를 순차적으로 vector에 push_back해준다.
  2. 그 후에 최소값인 2부터 자신을 제외한 배수는 모두 0으로 바꿔준다.
  3. 2의 배수들을 0으로 만들었다면 4의 배수들 또한 0일테니 만약 자기 자신이 0이 되어있는 상태라면 다음수로 넘어간다.
  4. 이를 반복하면 마지막에는 vector에 2부터 N까지의 소수, 0, 1이 남게 된다.
  5. 이제 모든 값들을 더한 후 1을 빼면 2부터 N까지의 소수들의 합이 나온다.
  • 수정된 코드 채점 결과

  • 소수를 구하는 가장 최적의 알고리즘을 찾을 수 있어서 좋았다.


저작자표시

'프로그래머스' 카테고리의 다른 글

level 2 - 124 나라의 숫자(100/100)  (0) 2019.03.28
level 2 - 타겟 넘버(100/100)  (0) 2019.03.28
level 1 - k번째수(100/100)  (0) 2019.03.24
level 1 - 모의고사(100/100)  (0) 2019.03.24
Level 1 - 완주하지 못한 선수(100/100)  (0) 2019.03.24

+ Recent posts

티스토리툴바