[알고리즘 연습] 소수의 개수 (by C++)

소수의 개수

• 자연수 N을 입력하면 1~N까지의 수 중 소수를 찾아 출력해준다.
• 예를 들어, 20이 입력되면 2, 3, 5, 7, 11, 13, 17, 19 총 8개의 소수가 출력된다.
• 시간 제한이 짧다고 가정하고 최대한 효율적인 알고리즘을 생각해보자.

---

풀이1

#include <stdio.h>
int a[200001];

int main() {
    //freopen("input.txt", "rt", stdin);
    int n, i, j, res = 0;

    scanf("%d", &n);

    for(i = 1; i <= n; i++) {
        for (j = i; j <= n; j += i) {
            a[j]++;
        }
    }

    for(i = 1; i <= n; i++) {
        if (a[i] == 2) res++;
    }

    printf("%d", res);


    return 0;
}

- 이전에 했던 방식을 참고하여, 1부터 배수들을 증가시켜 주면서 확인했다.

- '배수로 증가시킨 갯수 = 약수의 갯수' 이므로 2인 값만 확인하면서 갯수를 체크한다.

---

풀이2

#include <stdio.h>

int main() {
    //freopen("input.txt", "rt", stdin);
    int n, i, j, flag, res = 0;

    scanf("%d", &n);

    for(i=2; i<=n; i++) {
        flag = 1;
        for (j = 2; j*j <= i; j++) {
            if (i % j == 0) {
                flag = 0;
                break;
            }
        }
        if (flag == 1) res++;
    }

    printf("%d", res);    

    return 0;
}

- 수학적으로 어떤 수 N의 소수 여부를 판단할 때, N의 제곱근까지의 나누어떨어짐 여부만 판단하면 그 이후 숫자는 판단하지 않아도 된다. (이는 제곱근은 자신과, 그 이전의 수는 더 큰 수와 짝을 맞추고 있기 때문이다.)

- 이를 활용하여 반복문이 돌아가는 횟수를 현저히 줄인다.

---

 

풀이3 (풀이1 개선)

#include <stdio.h>
int a[200001];

int main() {
    //freopen("input.txt", "rt", stdin);
    int n, i, j, res = 0;

    scanf("%d", &n);

    for(i = 2; i <= n; i++) {
    	if (a[i] == 0) {
    		res++;
        }
    	for (j = i; j <= n; j += i) a[j]++;                
    }

    printf("%d", res);


    return 0;
}

- 1은 무조건 아니므로 제외하고, 2부터 시작해서 초기값이 0이면 결과값(소수의 개수)을 증가시킨다.

- 그리고 0 이면 해당 값의 배수를 전부 증가시킨다.

- 초기값이 0 일 경우만 소수의 개수를 증가시키므로 첫번째 방법과 비슷한 원리로 소수의 개수를 셀 수 있게 된다. (다만 아주 조금 더 효율적이다.)

- 이러한 방식을 '에라토스테네스의 체'라고 한다.