1929)소수 구하기

https://www.acmicpc.net/problem/1929

M이상 N이하 소수를 찾는 문제이다.

예전에는 isPrime() 함수로 소수를 찾았다.

i를 2부터 하나씩 증가시켜 n에 도달하기 전에 n이 i로 나누어 떨어지면 소수가 아니다.

어떤 수가 소수인지 알려면 못해도 2부터 n까지 나누어 봐야 한다.

그래서 isPrime()은 시간이 많이 걸린다.

문제는 더 짧은 시간 내에 소수를 찾을 것을 요구해서 다른 방법을 찾아야 했다.

소수를 구하는 방법중 쉬운 방법이 에라토스테네스의 체이다.

그래서 에라토스테네스의 체를 공부했는데 다음과 같은 방법으로 소수를 찾는다.

우선 2부터~n까지 수를 준비한다.

2가 소수라면 2의 배수는 소수가 아니기 때문에 제거한다.

3이 소수라면 3의 배수는 소수가 아니기 때문에 제거한다.

4는 제거됬기 때문에 넘어감.

5가 소수라면 5의 배수는 소수가 아니기 때문에 제거한다.

이것을 코딩하게 쉽게 말을 바꿔보면 아래와 같다.

처음에 n+1크기의 배열을 준비하고 모두 TRUE로 초기화한다.

2를 소수로 가정했기 때문에 2의 배수를 모두 FALSE로 바꾼다.

3도 소수로 가정했기 때문에 3의 배수를 모두 FALSE로 바꾼다.

4는 FALSE이기 때문에 넘어감..

n이하 모든 소수에 대해 위와 같은 과정을 수행할 필요는 없다.

n>=p^2인 p까지만 그 배수를 찾아 FALSE로 만들어주면 된다.

#include<stdio.h>
#define TRUE 1
#define FALSE 0
 
void eratos(int *primeSet, int N) {
    for (int i = 2; i < N; i++) {
        if (primeSet[i]) {
            int j = 2;
 
            while (i*j <= N) {
                primeSet[i*j] = FALSE;
                j++;
            }
        }
    }
}
 
int main() {
    int M,N;
    int *primeSet;
 
    scanf("%d %d", &M,&N);
    primeSet = (int *)malloc(sizeof(int)*(N + 1));
 
    for (int i = 2; i < N + 1; i++) {
        primeSet[i] = TRUE;
    }
 
    eratos(primeSet, N);
 
    for (int i = M; i <= N; i++) {
        if (primeSet[i] == TRUE) {
            printf("%d\n", i);
        }
    }
 
    return 0;
}