1929 - 소수 구하기

• 난이도: 실버 3
• 날짜: 2023년 2월 2일
• 상태: Correct
• 추가 검토 여부: Yes

solution

• 더 좋은 알고리즘이 있었던 것으로 기억하지만 에라토스테네스의 채 알고리즘의 단순 구현 버전으로 풀었다.
• 해당 범위 내에서 $start$부터 $\sqrt{end}$까지 1씩 증가시켜가며 나머지를 기반으로 소수 여부를 판별했다. 본 문제는 이 알고리즘으로도 해결되었으나, 이보다 훨씬 진보된 소수 탐색 알고리즘을 본 기억이 난다… 후에 참고하자
• 1은 소수가 아닌 것을 깜빡하고 1에 대한 예외처리를 하지 않아 오답이 나왔었다.

code

#include <iostream>
#include <cmath>
using namespace std;

bool isPrime(int input)
{
    if(input == 1) return false;

    for(int i = 2; i <=sqrt(input); i++)
	if(input % i == 0) return false;
    return true;
}

int main()
{
    int M, N;
    scanf("%d", &M);
    scanf("%d", &N);

    for(int i = M; i <= N; i++)
	if(isPrime(i)) printf("%d\n", i);

    return 0;
}

ref

1929번: 소수 구하기