JArchive 프로그래밍 일기

소수찾기 (에라토스테네스의 체)

에라토스테네스의 체 방식을 써야 효율성케이스까지 패스할 수 있는 문제다. (프로그래머스 level 1)

문제

문제링크

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

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

제한 조건: n은 2이상 1000000이하의 자연수입니다.

리뷰

n이 커지면 시간초과가 난다.
에라토스테네스의 체 를 이용해야한다.

구하려는 범위 크기 + 1만큼의 배열을 선언한다.

1000000 이라면, int arr[1000001]선언.

arr[0]과 arr[1]은 사용하지 않는다. 0과 1은 소수가 아니기 때문이다.

arr의 값이 0이면 소수, 1이면 소수가 아니다.

일단 arr배열의 값은 전부 0으로 초기화 하여 처음에는 소수라고 본다.

만일, arr[i]가 0이면(숫자 i가 소수라면), i이후의 i의 배수들은 i를 약수로 가진 수들이다.

따라서 i 이후의 i의 배수에 대해 1값을 준다. (소수가 아니다.)

arr[i]가 1이면 i는 이미 소수가 아니므로 i의 배수 역시 소수가 아니다.

이렇게 배수들을 제외한다.

어느 수의 배수라는 것은 소수가 아니라는 뜻이기 때문이다.

( 이 문장이 한 번에 이해가 안 됬었다, 그치만 직접 수를 써보면서 몇 번 다시 읽어보면 이해할 수 있었다. )

2가 소수라면(arr[2] == 0) , 2의 배수들을 지운다. (arr[2의배수들] == 1)

3이 소수라면 (arr[3] == 0), 3의 배수들을 지운다. (arr[3의 배수들] == 1)

이런식으로 진행한다.

지워야 할 수가 겹치는 문제

2의 배수들: 4, 6, 8, 10, 12, 14 를 지운다.

3의 배수들: 6, 9, 12, 15 .. 를 지운다.

6과 12처럼 지워야할 수의 겹침을 피하려면, 제곱한 수 부터 배수를 지우면 된다.

예를 들어, 5의 배수를 지워야한다면 5_2, 즉 10부터 지우는게 아니라 5의 제곱 25부터 지운다.

25 + (1 * 5), 25 + (2 * 5), 25 + (3 * 5) , ... 그러면 이전에 지워진 배수들을 건너 뛰게 된다.

코드

#include <stdio.h>
#include <vector>
using namespace std;

// 소수 찾기  프로그래머스  

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


int arr[1000001]; 
// arr[0]과 arr[1]은 사용하지 않는다.  0과 1은 소수가 아니기 때문. 
// 소수면 0, 소수가 아니면 1값을 갖는다. 

int solution(int n) {

    int answer = 0;
    int i = 0, j = 0;

    for (i = 2; i * i <= n; i++)
    {
        if (arr[i] == 0){ // i가 소수라면, i의 배수는 소수가 아니다.  

            // 유의: i의 제곱부터 지우기 시작한다.  
            for (j = i * i; j <= n; j += i)
                arr[j] = 1; // 소수가 아니므로 1값 할당. 
        }

    }

    for(i = 2; i <= n; i++){ // 소수로 남겨진 것들의 개수를 센다  
        if(arr[i] == 0) answer++;
    }

    return answer;
}

도움이 되셨다면 '공감'을 눌러주세요 :)