Java) BOJ 2581. 소수

February 13, 2022

문제 링크

자연수 M과 N이 주어질 때 M이상 N이하의 자연수 중 소수인 것을 모두 골라 이들 소수의 합과 최솟값을 찾는 프로그램을 작성하시오.
예를 들어 M=60, N=100인 경우 60이상 100이하의 자연수 중 소수는 61, 67, 71, 73, 79, 83, 89, 97 총 8개가 있으므로,
이들 소수의 합은 620이고, 최솟값은 61이 된다.

소수 구하기는 프로그래밍을 처음 배울 때 풀어봤던 문제이기도 하고 예전에 몇 번 풀어봐서 풀이를 떠올리는 것은 어렵지 않았다.
하지만 정직하게 2부터 i까지의 수의 나머지를 구하면서 소수를 판별하면 시간이 오래 걸리기 때문에 i의 제곱근 만큼만 반복하는 알고리즘을 썼다.
i의 제곱근만큼만 반복해도 소수인지 판별이 되는 이유는 제곱근을 넘어가는 수 부터는 앞전에 구했던 곱해서 i가 되는 수들이 순서만 바뀌어서 똑같이 나오기 때문이다.
예를 들어 i=16라면
1*16
2*8
4*4
8*2
16*1
위와 같이 16의 제곱근인 4를 기점으로 앞전에 나왔던 수들이 순서만 바뀌어서 나온다.
그래서 제곱근을 초과하는 수에 대해 소수를 판별하는 연산을 하는 것은 생략해도 결과에 영향이 없다.
C++ 소수 판별하기
예전에 참고했던 글인데 언어 상관없이 개념적으로 참고하기 좋은 글이다.
이 문제에서는 M 이상 ~ N 이하 범위의 수들을 반복문을 돌리면서 i번째 수가 소수라면 합계에 더해주고 그 중 가장 작은 값도 함께 저장했다.
입력의 최대값이 10,000이기 때문에 소수를 판별하는 알고리즘은 최대한 빠른 것을 사용했다.