백준_1929_소수구하기

입력받은 m과 n 사이의 소수를 구하는 문제입니다.

 

소수란, 약수가 1과 자기 자신인 수를 뜻하죠.

 

가장 흔하게, 2부터 자기 자신-1 까지 나누어지는지 검사하여 소수인지 판별합니다.

 

하지만 문제에서 1백만까지 입력받을 수 있기 때문에 위의 방법대로라면, 시간이 너무 오래 걸립니다.

 

 

 

여기서 소수의 성질을 하나 더 알아야 합니다.

 

소수는 자기 자신의 제곱근 이하의 자연수 로 나누었을 때 1을 제외하고 나누어떨어지지 않습니다.

 

ex) 16의 제곱은은 4이죠. 2 , 3 , 4 로 나누면 나누어 떨어지므로 소수가 아닙니다.

53의 제곱근은 7.xx 이죠. 2 , 3 , 4 , 5 , 6 , 7 중 어떤 것으로도 나누어 떨어지지 않으므로 소수입니다.

 

이제 이 방식을 코드로 구현해 봅시다.

 

 

전체 코드)

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

int decimal(int n);

int main(void)
{
    int a, b;
    scanf("%d %d", &a, &b);

    if (a == 1)
    {
        a++;
    }

    for (int i = a; i <= b; i++)
    {
        decimal(i);
    }
    return 0;
}

int decimal(int n)
{
    int temp = sqrt(n);
    for (int i = 2; i <= temp; i++)
    {
        if (n % i == 0)
        {
            return -1;
        }
    }
    printf("%d\n", n);
    return 1;
}

 

소수의 성질을 이용해 풀 수 있는 문제입니다.