[백준/BOJ] 백준 1929번 : 소수 구하기

www.acmicpc.net/problem/1929

1929번: 소수 구하기

에라토스테네스의 체를 이용해 소수인 것을 표시해서 소수를 구하였다.

 

코드

#include <iostream>
#include <algorithm>
using namespace std;

int check[1000001];
int m, n;

//에라토스테네스의 체를 이용해 n까지 수 중 소수인것을 1로 표시한다
void checkMake()
{
	for (int i = 0; i <= n; i++)
		check[i] = 1;

	check[0] = 0;
	check[1] = 0;

	for (int i = 2; i <= n; i++)
	{
		if (check[i] == 1)
		{
			for (int j = i + i; j <= n; j = j + i)
			{
				check[j] = 0;
			}
		}
	}
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> m >> n;

	checkMake();

	for (int i = m; i <= n; i++)
	{
		//i가 소수일때
		if (check[i] == 1)
			cout << i << "\n";
	}

	return 0;
}