백준 2581 소수 / C++

문제 : 2581

풀이 point

60부터 100이하의 수들을 1부터 수-1까지 나누어서 소수인지 판단한다.

사실 이떄 소수를 판단하기 위해 1부터 수-1까지 나누어 볼 필요는 없다.
1부터 제곱근까지만 봐도 된다.(약수는 대칭적 성질이기 때문이다.)

ex) 12 : 1 2 3 4 6 12

코드

//백준 2581, 소수
#include <iostream>
#include <cmath>

int main(){

    int M, N; int sum{0}; int min{10'001};
    std::cin >> M >> N;
    
    while(M <= N){
        int i{2}; bool flag = M == 1 ? true : false; 
        while(i <= std::sqrt(M)){ //제곱근까지만 봐도 됨(약수는 대칭적 성질이기 때문)
            if(M%i == 0){
                flag = true;
                break;
            }
            ++i;
        }
        if(!flag){
            sum+= M;
            min = std::min(min, M);
        }
        ++M;
    }
    if(sum == 0) std::cout << -1;
    else std::cout << sum << '\n' << min;
    
    return 0;
}