(C언어)백준 2960. 에라토스테네스의 체

문제

에라토스테네스의 체는 N보다 작거나 같은 모든 소수를 찾는 유명한 알고리즘이다.

이 알고리즘은 다음과 같다.

1. 2부터 N까지 모든 정수를 적는다.
2. 아직 지우지 않은 수 중 가장 작은 수를 찾는다. 이것을 P라고 하고, 이 수는 소수이다.
3. P를 지우고, 아직 지우지 않은 P의 배수를 크기 순서대로 지운다.
4. 아직 모든 수를 지우지 않았다면, 다시 2번 단계로 간다.

N, K가 주어졌을 때, K번째 지우는 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ K < N, max(2, K) < N ≤ 1000)

출력

첫째 줄에 K번째 지워진 수를 출력한다.

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


int main(void)
{
    int n = 0, k;
    scanf_s(" %d %d", &n, &k);
    int i = 0, j = 0;
    int* prime = (int*)malloc(sizeof(int) * (n + 1));    //배열 동적할당
    int count = 0;

    for (i = 0; i <= n; i++)                    //각 요소 초기화
    {
        prime[i] = i;
    }
    
    for (i = 2; i <= n; i++)
    {
        if (prime[i] == 0)                    //배열 요소가 0이면 소수가 아니므로 건너뜀
            continue;
        
        for (j = i; j <= n; j += i)    //에라토스테네스의 체 적용. 소수가 아니면 0 대입
        {
            if (prime[j] != 0)
            {
                prime[j] = 0;
                count++;
            }
            if (count == k)
                goto end;
        }
    }
end:

    printf("%d\n", j);

    return 0;
}

 

에라토스테네스의 체가 무엇인지는

 

https://kiffblog.tistory.com/34

(C언어)프로젝트 오일러(Project Euler)10. 이백만 이하 소수의 합

프로젝트 오일러를 풀면서 설명했다. 

 

9~17행: 배열을 입력받은 수에 맞게 할당하고, 각 요소를 초기화한다. 

24~29행: 배열에 0을 대입하여 지우는 것과 마찬가지 의미를 갖도록 했다. prime[j]에 해당하는 요소가 0이 아니라면, 즉 아직 지워지지 않았다면 0을 대입해 지운다. 지울 떄마다 count를 늘려 횟수를 센다.

31행: count가 k와 같아지면 목표로 한 횟수에 도달했다는 의미이므로 goto문으로 중첩반복문을 빠져나온다.

37행: count == k일 때 k번째 수를 가리키는 변수는 j이므로 j를 출력한다. 

 

예) n = 10, k = 7일 때

외부 반복문이 첫 번째 루프를 끝냈을 떄, 즉 i = 2일 때

두 번째 반복문이 실행되고 count가 7이 되었을 때. j값은 9이다.