[Baekjoon] Class2 09 - 소수 구하기 [1929]

소수 구하기 [1929번]

M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.

출력

한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.

생각해볼점

is_prime함수에서 소수를 판별할 때 사용한 방법은 다음과 같다.

1. 판별하고자 하는 숫자 num이 1이거나, 혹은 2가 아니면서 2로 나누어지는 수일 경우 소수가 아니다.
2. 그 외에는 num을 3부터 시작하는 수 i로 나누어본다. 나누었을 때 나머지가 없다면 해당 수는 소수가 아니다.
3. 반복은 i가 num의 제곱근 이상이 될 때 까지 진행된다. 제곱근 이후부터는 제곱근 이전에 검사했던 i들과 짝을 이루기 때문에 검사할 필요가 없다.

이렇게 판별한 소수들을 에라토스테네스의 채를 이용해 인덱싱했다.
위키피디아 링크
과정은 다음과 같다.

1. 2부터 시작한다. 2는 소수이므로, 2와 2의 배수들을 모두 지운다. 코드 상에서는 배열의 값을 0으로 바꾸는 것으로 했다.
2. 남은 수중에 가장 작은 수가 소수인지 판별한다. 3이므로, 3과 3의 배수들을 모두 지운다.
3. 또다시 남은 수중에 가장 작은 수를 판별하고, 소수일경우 그 수와 배수들을 모두 지운다. 이 과정을 반복하는데, 이 때 판별할 수는 찾고자하는 범위의 최대값의 제곱근까지면 된다.

코드 구현

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

static int	is_prime(int num)
{
	int	i = 3;

	if ((num != 2 && num % 2 == 0) || num == 1)
		return (0);
	while (i * i <= num)
	{
		if (num % i == 0)
			return (0);
		i += 2;
	}

	return (1);
}

int main()
{
	int	m, n, idx, temp;
	int	*arr;

	scanf("%d %d", &m, &n);
	arr = (int *)malloc((n + 1) * sizeof(int));
	
	idx = -1;
	while(++idx <= n)
		arr[idx] = idx;

	idx = 2;
	while(idx * idx <= n)
	{
		if (is_prime(idx) == 1)
		{
			temp = 2;
			while(idx * temp <= n)
			{
				arr[idx * temp] = 0;
				temp++;
			}
		}
		if (idx == 2) // 2일 경우에는 다음번 가장 작은 수가 3이다.
			idx++;
		else // 그 외에는 이미 짝수가 모두 지워졌으므로, 2씩 올려가며 찾으면 된다.
			idx += 2;
	}

	while (m <= n)
	{
		if (arr[m] > 1)
			printf("%d\n", arr[m]);
		m++;
	}

	free(arr);
	return (0);
}