1929번: 소수 구하기 (c언어)

# 문제

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

1929번: 소수 구하기

• M이상 N이하의 소수를 모두 출력
• 1 <= M <= N <= 1,000,000

 

---

# 풀이

'에라토스테네스의 체'를 이용하여 소수를 구하는 방법이다. 이 방법을 이용하면 많은 양의 소수를 빠르게 구할 수 있다.

('에라토스테네스의 체'란? https://ko.wikipedia.org/wiki/에라토스테네스의_체)

 

0. 해당 인덱스값이 소수이면 0, 소수가 아니면 1로 저장한 뒤 해당 인덱스 위치의 값으로 출력여부를 판단한다.

예를 들어 tmp[1]일때, 1은 소수가 아니므로 1로 저장될 것이고 tmp[2]라면 2는 소수이기때문에 0으로 저장될 것이다.

 

1. N까지 미리 배열을 생성하고 0으로 초기화한다. (인덱스 1은 소수가 아니므로 1로 초기화한다.)

 

2. 2부터 N의 제곱근( sqrt(N) )까지 반복문을 돌린다.

 

3. 반복문은 tmp[i]가 0일 경우. 즉, tmp[i]가 소수일 때 sieve_of_erathosthenes함수로 이동한다.

 

4. 만약 i가 2라고 했을 때, 2도 1로 바뀌어 소수가 아니라고 판단이 되기때문에 n * n부터 시작하여 N까지 n만큼 증가하면서 탐색하면서 값을 1로 바꿔준다.

n만큼 증가시키는 이유는 하나씩 탐색하는게 아닌 배수값만 바꿔주기 위해서이다. (시간의 차이가 심함. 아래에서 자세히 설명)

 

5. tmp 배열에서 값이 0인 인덱스 값을 출력한다.

 

---

# 소스코드

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

void	sieve_of_erathosthenes(int *tmp, int n, int N)
{
	for (int i = n * n; i <= N; i += n)
		tmp[i] = 1;
}

int	main(void)
{
	int	tmp[1000001] = {1, 1};
	int	M, N;

	scanf("%d %d", &M, &N);
	// input number
	for (int i = 2; i <= sqrt(N); i++)
	{ 
		if (!tmp[i])
			sieve_of_erathosthenes(tmp, i, N);
	}

	// print
	for (int i = M; i <= N; i++)
	{
		if (tmp[i] == 0)
			printf("%d\n", i);
	}
	return (0);
}

---

# 회고

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

void	sieve_of_erathosthenes(int *tmp, int n, int N)
{
	for (int i = 2; i <= N; i++) // 이 부분에서 큰 차이가 발생했다.
	{
		if (!tmp[i] && (i != n) && (i % n == 0))
			tmp[i] = 1;
	}
}

int	main(void)
{
	int	tmp[1000001] = {1, 1};
	int	M, N;

	scanf("%d %d", &M, &N);
	// input number
	for (int i = 2; i <= sqrt(N); i++)
	{ 
		if (!tmp[i])
			sieve_of_erathosthenes(tmp, i, N);
	}

	// print
	for (int i = M; i <= N; i++)
	{
		if (tmp[i] == 0)
			printf("%d\n", i);
	}
	return (0);
}

'에라토스테네스의 체'는 소수 n을 발견하면 그 다음 n의 배수 위치에 존재하는 값을 지워준다.

내가 작성한 코드는 2부터 N까지 1씩 증가하면서 n으로 나눴을 때 나머지가 0인 값을 지워준다.

이 차이에서 약 300ms ~ 500ms정도 시간의 차이가 났다. 

 

예를 들어 1부터 100까지 숫자 중에서 소수를 찾아야할 때, 2를 발견하고 2의 배수에 있는 값을 지워줘야한다고 하면

'에라토스테네스의 체'는 50번만 움직이면 된다. 하지만 내가 작성한 코드는 숫자 하나하나 다 확인하기 때문에 100번을 움직이게 된다.

 

N이 커질수록 이 차이는 더 커지게 되는 것이다.