코딩 테스트 준비 1단계 기본기 - 백준 2581

 

코딩테스트 대비를 위해 도움이 될만한 문제 추천 블로그가 있어서 이 단계대로 코테를 준비합니다.

참조 사이트: http://covenant.tistory.com/224

코딩테스트 대비를 위한 백준 문제 추천

Part 1 준비운동 - 소수 (백준 2581)

문제 출처: https://www.acmicpc.net/problem/2581

2581번: 소수

풀이

에라토스테네스의 체를 이용하면 되고, 20행에서 최솟값을 비교하는 min변수를 사용함으로써 소수의 최솟값을 구하기 위해 또 m부터 n까지 수 중 가장 작은 수를 구하기 위해 반복문을 돌려야 하는 불필요 연산을 방지할 수 있습니다. 

코드

#include<iostream>
using namespace std;
int arr[10001];
int main()
{
    int m, n, sum = 0;
    arr[0] = 1, arr[1] = 1;
    for (int i = 2; i <= 10001; i++)
        for (int j = i * i; j <= 10001; j += i)
        {
            if (arr[j] == 1)continue;
            arr[j] = 1;
        }
    cin >> m >> n;
    int min = 10001;
    for (int i = m; i <= n; i++) {
        if (arr[i] == 0)
        {
            sum += i;
            if (min > i)min = i;
        }
    }
    if (sum) {
        cout << sum << endl;
        cout << min << endl;
    }
    else
        cout << -1 << endl;
 
    return 0;
}

 

결과