[C++] 소수 구하기 (에라토스테네스의 체)

www.acmicpc.net/problem/1929

1929번: 소수 구하기

 

위 문제를 풀어보다가

 

redcoder.tistory.com/48

[C++] 소수 구하기 (에라토스테네스의 체)

를 참고했다.

 

 

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	int m=0, n=0;


	cin >> m >> n;

	bool * arr = new bool[n]; //최대 범위크기만큼 동적배열 지정 (단점 메모리 낭비)

	for (int i = 2; i <= n; i++) //모든 배열 true
		arr[i] = true;

	for (int i = 2; i * i <= n; i++)
	{
		if (arr[i] == false) { //이미 소수가 안되는 수 판별 false
			continue; //18줄 for문으로
		}

		if (arr[i] == true){
			for (int j = i * i; j <= n; j += i)
				arr[j] = false;
        }
	}
	
	for (int i = m; i <= n; i++) { //정한 범위내에서만 
		if (arr[i]) //소수인수 출력 
			cout << i << "\n";
	}


	return 0;

}