[백준/C & C++] 1929 소수 구하기

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

1929번: 소수 구하기

코드 (C)

#include <stdio.h>

int arr[1000001] = {0,};

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

	arr[1] = 1;
	for (int i = 2; i <= m; i++)
	{
		if (arr[i] == 1) continue;
		else for (int j = i * 2; j <= m; j+=i) arr[j] = 1;
	}

	for (int i = n; i <= m; i++) if (arr[i] == 0) printf("%d\n", i);

	return 0;
}

코드 (C++)

#include <iostream>
using namespace std;

int arr[1000001] = { 0, };

int main()
{
	int n, m;
	cin >> n >> m;

	arr[1] = 1;
	for (int i = 2; i <= m; i++)
	{
		if (arr[i] == 1) continue;
		else for (int j = i * 2; j <= m; j += i) arr[j] = 1;
	}

	for (int i = n; i <= m; i++) if (arr[i] == 0) cout << i << "\n";

	return 0;
}

코드 설명

에라토스테네스의 체를 이용해 풀면 된다. 이는 소수의 배수는 전부 소수가 아님을 이용하는 것이다. 

위 코드에서 1은 소수가 아님을, 0은 소수임을 뜻한다. 

1은 소수가 아니므로 먼저 arr[1] = 1로 해준다. 

2부터 m까지 반복문을 돈다. 앞서 배열을 선언할 때 0으로 초기화해두었으므로 2는 else문에 걸리고 짝수 인덱스에 저장된 값은 모두 소수가 아닌 것으로 저장한다. m까지 계속 반복문을 도는데, 만약 인덱스에 저장된 값이 1이라면 소수가 아니라는 뜻이므로 바로 다음 수를 확인하다. 

 

느낀 점

직전에 포스팅한 문제는 숫자를 2부터 숫자-1까지 일일이 나눠 보며 확인했다면 이 문제는 에라토스테네스의 체를 이용해 더 빠른 속도로 소수를 출력할 수 있다.