[21401][伯俊/BOJ]救出1929号小数

質問する

にゅうしゅつりょく

に答える

小数は1と自分の数だけを意味します.逆に、いくつかの倍数は少数ではありません.それを活用したのはエラトネスのふるいです.エラトニスのふるいは自分以外の自分の排水を除いて、少数の方法を探しています.
従って、エラトネスのふるいで問題を解決することができる.

iが2の場合、2の倍数4 6 8 10 12...クリア

iは3時3の倍数6 9 12 15 18...クリア

iは4時4の倍数8121620...クリア

3−3を繰り返すと少数を求めることができ,時間複雑度はO(nlog logn)である.

https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

コード#コード#

#include <bits/stdc++.h>
using namespace std;
#define SIZE 1000002

bool p_list[SIZE];

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);	
	
	int m, n;
	cin >> m >> n;

	for (int i = 2; i <= n; ++i) // 0과 1은 0으로 나머지는 1로 초기화
		p_list[i] = 1;

	for (int i = 2; i <= n; ++i) // 2부터 입력값까지
	{
		if (p_list) // true 라면
		{
			// i가 2라면 4 6 8 10.. 0
			// i가 3이라면 6 9 12 15.. 0
			// i가 k라면 2*k 3*k 4*k.. 0
			// 이렇게 자기 자신의 2배 값부터 지워나감
			for (int j = 2 * i; j <= n; j += i) 
				p_list[j] = 0;
		}
	}
	
	for (int i = m; i <= n; ++i)
		if (p_list[i])
			cout << i << ' ';
}