개인공부용123 프로그래밍 블로그

[백준] 1929 (에라토스테네스의 체) 본문

알고리즘문제

[백준] 1929 (에라토스테네스의 체)

개인공부용123 2017. 5. 2. 19:00

소수찾기문제는 유명한 알고리즘인 에라토스테네스의 체를 이용하면 쉽게풀수있습니다.


에라토스테네스의 체의 최악 수행시간은 O(N*log(logN))이라고합니다.



#include <iostream>
#include <math.h>
using namespace std;

int main() { // 에라토스테네스의 체를 이용한 소수 구하기
	std::ios::sync_with_stdio(false);
	int M, N; // M <= N

	cin >> M >> N;

	bool* arr = new bool[N + 1];

	for (int i = 2; i <= N; ++i) {
		arr[i] = true;
	}

	int sqrt_N = (int)sqrt(N);

	for (int i = 2; i <= sqrt_N; ++i) {
		if (arr[i] == true) {
			for (int j = i; i*j <= N; ++j) {
				arr[i*j] = false;
			}
		}
	}

	for (int i = M; i <= N; ++i) {
		if(arr[i] == true) cout << i << endl;
	}

	return 0;
}


'알고리즘문제' 카테고리의 다른 글

[백준] 9012  (0) 2017.05.02
[백준] 1874(스택)  (0) 2017.05.02
[백준] 9426(세그먼트 트리)  (0) 2017.04.29
AlgoSpot) GRADUATION  (0) 2017.03.16
AlgoSpot) PASS486  (0) 2017.02.20