#12921 에라토스테네스의 체

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

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

 

1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.

소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
(1은 소수가 아닙니다.)

제한 조건

• n은 2이상 1000000이하의 자연수입니다.

입출력 예

nresult

10	4
5	3

입출력 예 설명

입출력 예 #1
1부터 10 사이의 소수는 [2,3,5,7] 4개가 존재하므로 4를 반환

입출력 예 #2
1부터 5 사이의 소수는 [2,3,5] 3개가 존재하므로 3를 반환

 

-------------------------------------------------------------

연습문젠데 가볍지 뭐~ 하면서 이중 for문으로 풀었다가 시간 초과가 떠 버렸다.

더 쉬운 방법이 있는 건가 싶어 질문탭을 보고 '에라토스테네스의 체'라는 알고리즘을 알게 됐다.

 

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

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

한마디로 소수 2부터 시작해서 소수값의 배수를 소수가 아닌걸로 판명지으는 과정을 계속 반복하는 것이다.

그러기 위해서는 배열값이 필요하다

 

#include <string>
#include <vector>

using namespace std;

int solution(int n) { //에라토스테네스의 체
    int sum = 0;
    bool* PrimeArray = new bool[n+1]; //2부터 ~ n-1까지 저장하는 배열 할당
    
    for( int i = 2 ; i <= n ; i++){ 
       PrimeArray[i] = true; //일단 전부다 소수라고 가정
    }
    
     for( int i = 2 ; i*i <= n ; i++){ 
       if (PrimeArray[i]) //prime값 i의 배수에 대해 false값을 준다
           for( int j = i*i ; j <=n ; j +=i)
               PrimeArray[j] = false;
    }
    
    for( int i = 2 ; i <= n ; i++){ 
       if( PrimeArray[i])
           sum++;
    }
    return sum;
}

처음에는 전부 다 true(소수)로 초기화한다

그리고 2부터 3, 5, .... 의 배수를 다 false(소수x)로 할당한다

그리고 true의 개수를 반환하면 된다.