프로그래머스 : 소수 찾기 [C++]

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/12921

 

문제 설명

1. 1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.
2. 소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
3. (1은 소수가 아닙니다.)

문제 입출력 예)

n	result
10	4
5	3

 

문제 풀이

문제를 어떻게 풀어야할지 생각하다가, 너무 비효율적인 풀이라서 문제풀이를 포기했었다,,

내가 생각한 문제풀이는 for문을 돌려서 그 내용이 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

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

출처 : 위키백과

알고리즘 방법

1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당한다.

2. 2는 소수이므로 오른쪽에 2를 쓴다. (빨간색)

3. 자기 자신을 제외한 2의 배수를 모두 지운다.

4. 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. (초록색)

5. 자기 자신을 제외한 3의 배수를 모두 지운다.

6. 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. (파란색)

7. 자기 자신을 제외한 5의 배수를 모두 지운다.

8. 남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다. (노란색)

9. 자기 자신을 제외한 7의 배수를 모두 지운다.

10. 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다.

 

결론 : 120보다 작거나 같은 수 가운데 2, 3, 5, 7의 배수를 지우고 남는 수는 모두 소수이다.

#include <string>
#include <vector>
 
using namespace std;
 
int solution(int n) {
    int answer = 0;
    vector<bool> v(n, true);
    
    for(int i=2; i<=n; i++){
        if(v[i] == true){
            for(int j=2; i*j<=n; j++){
                v[i*j] = false;
            }
            answer++;
        }
        
    }
    
        
    
    return answer;
}

 

리뷰

소수 알고리즘 : 에라토스테네스 고대 학자,, 메모