[백준] 1929 with C++

문제설명

---

입출력 예제

---

개념

　자연수 M과 N 사이의 소수를 찾는 문제다. 소수를 구하는 알고리즘을 효율적으로 구하지 않는다면, 시간 초과가 걸리는 문제다. 

---

풀이(1)

#include <iostream>

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

	int m, n;
	std::cin >> m >> n;

	for (int i = m; i <= n; i++)
	{
        if (IsPrime(i))
            std::cout << i << '\n';
	}
}

　시간 초과 문제를 미연에 방지하기 위해 std::ios::sync_with_stdio(false); std::cin.tie(NULL)를 이용한다.

그리고 M과 N을 입력받고, 각 반복마다 IsPrime() 함수를 호출하여, 이 조건에 만족하는 소수면 그 수를 출력하게 하면 된다.

 

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

　다음은 소수인지 판단하는 IsPrime() 함수다. 여기서 핵심인 것은 2 이상 n이하의 수 일 때 반복문의 조건이다.

 

for (int i = 2; i * i <= n; i++)

　현재 검사하는 숫자 i가 소수인지 판별하기 위해 2부터 i-1까지의 수로 나누어 보지 않고, i의 제곱근까지만 나누고 있다. 만약 i의 제곱근보다 큰 약수가 존재한다면, 그 약수의 반대편 약수도 존재하므로, 이 둘 중 하나는 반드시 i의 제곱근보다 작거나 같아야 한다. 따라서 i의 제곱근까지만 검사해도 소수를 판별할 수 있다. 이 방법을 사용하면 시간 복잡도가 O(√n)으로 매우 효율적이다.

 

총합본

#include <iostream>

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

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

	int m, n;
	std::cin >> m >> n;

	for (int i = m; i <= n; i++)
	{
        if (IsPrime(i))
            std::cout << i << '\n';
	}
}