백준 2581 - 소수 판별 문제

#include <stdio.h>
#include <stdlib.h>

int main() {
    int m, n;
    int min=0, sum=0;

    scanf("%d", &m);
    scanf("%d", &n);

    for(int num=m;num<=n;num++) {
        for(int i=1;i<=num;i++) {
            if(i==1) continue;
            else if( (i < num) &&(num%i == 0) ) break;
            else if(i == num) {
                 sum += num;      
                 if(min==0) min = num;
            }
        }
    }

    if(min == 0 || sum == 0)
        printf("-1");
    else
        printf("%d\n%d\n", sum, min);
}

나는 단순하게 이렇게 접근을 했는데, 수학을 알고 아래의 원리를 사용하면 조금 더 쉽게 짤 수 있다.

 

    // 만약 어떤 수 p가 소수라면

    // 1을 제외한 숫자이면서 sqrt(p) 보다 작거나 같은 수들이

    // p의 약수가 아니면 된다.

    // 왜냐하면, p = sqrt(p) * sqrt(p)로 표현 가능하고, 만약 1이 아닌 약수가 존재한다면

    // 약수 하나는 최소한 sqrt(p)보다 작을 것이기 때문이다