백준 1929번 C언어 풀이

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

1929번: 소수 구하기

주어진 범위 내에서 소수들을 출력하는 문제.

 

알고리즘 자체는 쉬우나, 소수 판별의 경우 판별해야 하는 수가 매우 커질수록 엄청난 시간이 소요된다.

 

이를 해결하기 위해 최대한 시간을 줄여보려고 하였다.

 

사용되는 방법들은 보통 A라는 수를 2부터 A-1까지 나눠보면서 나누어 떨어지는 수가 발견되면 합성수로 판단하면 된다.

 

하지만 A가 커지면 커질수록 이 판단하는데 소요되는 시간이 길어질 뿐더러, 만약 A가 무진장 큰 소수인 경우, 2부터 A-1까지 한번씩 나눠야 한다.

 

이를 조금이나마 해결해보고자, 나누는 범위를 좁혀보았다.

 

A 는 곧 a*b (a, b는 자연수)의 형태로 나타나게 되는데, a가 결정되면 b가 자동으로 결정되므로, 우리는 a에만 신경써보자.

 

이때의 a가 A의 약수들을 모두 검사할 수 있는 최솟값은 sqrt(a)가 될 것이다.

 

이를 적용하여 다음과 같이 풀었다.

 

#include <stdio.h>
#include <math.h>
#include <stdbool.h>

bool prime_num (int num) {
    int size = floor(sqrt(num));
    bool ret = true;
    
    if (num == 1) {
        ret = !ret;
    } else {
        for (int i = 2; i <= size; i++) {
            if (num % i == 0) {
                ret = !ret;
                break;
            }
        }
    }
    return ret;
}

int main () {
    int m, n;
    scanf("%d%d", &m, &n);

    for (int i = m; i <= n; i++) {
        if (prime_num(i)) printf("%d\n", i);
    }
}