백준 2581번 (C++)

www.acmicpc.net/problem/2581

2581번: 소수

 

<답안>

#include <iostream>
using namespace std;
int main()
{
    int m,n;
    int min, sum = 0;
    cin>>m>>n;
    min = n;
    for(int i=m; i<=n; i++)
    {
        for(int j=2; j<=i; j++)
        {
            if(i%j == 0)
            {
                if(i == 2)
                {
                    min = 2;
                    sum += 2;
                }
                break;
            }
            else
            {
                if(j == i-1)
                {
                    if(i < min)
                        min = i;
                    sum+=i;
                }
            }
        }
    }
    if(sum == 0)
        cout<<-1;
    else
        cout<<sum<<"\n"<<min;
    
    return 0;
}

 

<설명>

min값은 가장 작아야 하기에 n으로 먼저 초기화를 시킨다

입력된 m부터 n까지 i를 1씩 증가시키며 2부터 i-1까지 나눈 나머지를 비교하여

i-1까지 배수로 나눠지지 않는 경우는 소수이므로 count를 증가시키면 된다

 

라는게 가장 기본적인 원리지만, 2가 입력되는 경우 이런 알고리즘으로는 불가한 상황이였다

 

그래서, 2부터 i까지 나눈 나머지를 비교하도록 수정하고

나눠지는 경우 중에서 i값이 2인경우는 소수가 맞으므로

min값을 2로, sum 를 2증가시키는 것을 추가하였다

 

최종적으로 구해진 sum값과 min 값을 출력한다