[BOJ] 1929번: 소수 구하기

문제 링크

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

접근한 방식

에라토스테네스의 접근으로 해결하였다. 내용은 다음과 같다.
주어진 자연수 N이 소수이기 위한 필요충분 조건은 N이 N의 제곱근보다 크지 않은 어떤 소수로도 나눠지지 않는다. 수가 수를 나누면 몫이 발생하게 되는데 몫과 나누는 수, 둘 중 하나는 반드시 N의 제곱근 이하이기 때문이다.

코드

<C++>

#include <iostream>
#include <cmath>
#define endl '\n'

using namespace std;

int M, N;

bool isPrime(int n) {
	if (n == 1) {
		return false;
	}
	for (int i = 2; i <= sqrt(n); i++) {
		if (n % i == 0) {
			return false;
		}
	}
	return true;
}

int main() {
	cin >> M >> N;

	for (int i = M; i <= N; i++) {
		if (isPrime(i)) {
			cout << i << endl;
		}
	}

	return 0;
}