정올 2813 : 소수의 개수 (+ 에라토스테네스의 체)

두가지 방법을 이용하여 해결할 수 있다.

1. 범위내의 모든 수들이 소수인지 아닌지 확인하여 소수의 개수를 카운트 하는 방법

2. '에라토스테네스의 체' 이용

 

1. 일반적인 방법

소수일때는 1, 소수가 아닐때는 0을 반환한다.

#include <stdio.h>
#include <math.h>

int prime(int x) {
    if (x == 1)return 0;
    for (int i = 2; i <= sqrt(x); i++) {
        if (x % i == 0)
            return 0;
    }
    return 1;
}


int main() {
    int m, n;
    int cnt = 0;
    scanf("%d %d", &m, &n);

    for (int i = m; i <= n; i++) {
        cnt += prime(i);
    }
    printf("%d\n", cnt);
}

 

2. 에라토스테네스의 체 이용

예시로 1부터 30까지의 소수를 구하는 과정을 살펴보면 아래와 같다.

그런데 한가지 더 생각해 볼 것이 있다.

4번에서 5의 배수를 걸러내는 과정에서 

5 * 2 = 10

5 * 3 = 15

5 * 4 = 20

5 * 5 = 25

5 * 6 = 30

 

위와 같이 걸러낼 값이 5개가 있는데 10은 2의 배수일 때, 15는 3의 배수일 때, 20은 4의 배수일 때 이미 모두 제거가 된다. 즉, 5보다 작은 수를 곱해서 생기는 5의 배수는 5를 처리하기 전에 이미 모두 제거가 되어있다. 따라서 5를 처리할 때에는 5의 제곱인 25부터만 처리하면 된다. 그 다음에 7을 처리할 때는 7의 제곱이 49로 30을 초과하기 때문에 더 이상 처리할 게 없으므로 그 때까지 제거되지 않고 남아있는 7,11,13,17,19,23,29 는 모두 소수가 된다.

 

이렇게 에라토스테네스의 체를 이용하여 어떤 수 n까지의 소수를 구하기 위해서, n의 제곱근까지만 배수를 걸러내는 작업을 하면 되므로 매우 빠른 속도로 소수를 구할 수 있다.

 

-> 소수를 저장할 배열(int prime[2000000]={0,};)을 적당히 선언 후 0으로 초기화 한다.

-> 배열의 인덱스의 값이 소수이면 0, 소수가 아니면 1을 넣을 것이다.

-> 0과 1은 소수가 아니므로 처음에 prime[0]=prime[1]=1; 을 작성하여 미리 1로 초기화 해둔다.

-> 2부터 n의 제곱근까지 각각의 배수를 인덱스로 가지고 있는 배열의 값을 1로 바꾼다.

-> 이 때, 각 수의 제곱부터만 처리하면 된다.

-> 추가로 증감식도 주의하자!

#include <stdio.h>
#include <math.h>

void eratos(int prime[],int n) {
	
	prime[0] = prime[1] = 1; // 소수가 아님
	for (int i = 2; i <= sqrt(n); i++) {
		if (prime[i] == 0) {  // i의 배수 제거
			for (int j = i * i; j <= n; j += i) { // i만큼 증가 주의!!
				prime[j] = 1;
			}
		}
	}

}

int main() {
	int m, n;
	int cnt = 0;
	int prime[2000000] = { 0, };
	scanf("%d %d", &m, &n);

	eratos(prime, n);

	for (int i = m; i <= n; i++) {
		if (prime[i] == 0)cnt++;
	}
	printf("%d\n", cnt); // 소수의 개수 출력

	return 0;
}