백준 - 2581번 소수(수학, 정수론, 소수 판정)

문제

자연수 M과 N이 주어질 때 M이상 N이하의 자연수 중 소수인 것을 모두 골라 이들 소수의 합과 최솟값을 찾는 프로그램을 작성하시오.

예를 들어 M=60, N=100인 경우 60이상 100이하의 자연수 중 소수는 61, 67, 71, 73, 79, 83, 89, 97 총 8개가 있으므로, 이들 소수의 합은 620이고, 최솟값은 61이 된다.

입력

입력의 첫째 줄에 M이, 둘째 줄에 N이 주어진다.
M과 N은 10,000이하의 자연수이며, M은 N보다 작거나 같다.

출력

M이상 N이하의 자연수 중 소수인 것을 모두 찾아 첫째 줄에 그 합을, 둘째 줄에 그 중 최솟값을 출력한다.
단, M이상 N이하의 자연수 중 소수가 없을 경우는 첫째 줄에 -1을 출력한다.

C++ 풀이

문제 그대로 소수 판정하는 함수를 별도로 구현하여 풀이하였다.

#include <bits/stdc++.h>

using namespace std;
int prime_check(int n){
    if (n==1) return 0; 	// 숫자 1은 소수X
    for(int i=2;i<=sqrt(n);i++){ // 2부터 나눠서 원래 수의 제곱근까지만 확인하면 된다.
        if (!(n%i)) return 0;
    }
    return 1; // return이 안될 경우 소수로 판정
}
int main()
{
    int M,N,tot=0,mn=100001;
    cin >> M >> N;
    for(;M<=N;M++){
        if (prime_check(M)) {
            tot+=M;
            if (mn > M)
                mn=M;
        }
    }
    (tot)?cout<<tot<<'\n'<<mn:cout<<-1;
    return 0;
}

숏코딩 분석하기

가독성 버전

이중 for 문을 통해 소수 판정 검사를 하였다.

#import<iostream>
int n,m,s,i,r;
main(){
    /*
    n 과 m을 받아서 n을 1씩 증가시키면서 m과 같아질 때까지 for 문 돌림.
    삼항연산자인 `n-i?:(r?:r=n,s+=n)`는 
    n-i값을 점검하는데 true인 경우 즉, 0이 아닌 값인 경우
    아무것도 하지 않고(=소수가 아님) 
    n-i=0, 즉 i가 n인 경우는 n이 소수이기 때문에
    콜론(:) 다음이 실행된다.
    `(r?:r=n)` 이 삼항연산자는 r에 가장 작은 소수값인 첫 소수 값
    을 할당하는 역할을 한다.
    `s+=n`은 소수의 합을 계산하는 역할이다.
    for 문 안의 다음 `for(i=2;i<n&&n%i++;);` 문은 
    i를 2부터 늘려가면서 i가 n과 같지 않으면서, n으로 나눴을 때 나머지가 있을 때 까지 돌리게 되는데, 즉 나머지가 없어서 0이 되는 경우
    해당 for loop가 끝나게 되고, 이때의 n-i값을 구하게 되면
    항상 true 값이 되어 소수가 아닌 상황이 되고,
    반대로 소수인 경우 i가 n과 같아져서 n-i값이 0이 된다.
    즉 소수를 판별하는 for loop라고 할 수 있다.
    마지막으로 `printf(r?"%d %d":"-1",s,r)`
    이 출력문을 통해 r이 0이 아닌 경우는 합계(s)와 최소값(r)을,
    r값이 갱신이 안된 경우 -1을 출력한다.
    */
    
    for(std::cin>>n>>m;n<=m;n-i?:(r?:r=n,s+=n),n++)
        for(i=2;i<n&&n%i++;);
    printf(r?"%d %d":"-1",s,r);}