문제

https://www.acmicpc.net/problem/2581

설명

이 문제는 어느정도 수학적 지식을 가지고 있다면 접근하기 더 수월해진다. 소수를 구별하는 방법에는 여러가지가 있는데 특히 특정 범위내의 소수를 구별하는데에는 [에라토스테네스의 체] 를 이용하면 더 수월하게 풀 수 있다.먼저 사용자가 입력될 수 있는 값은 아무리 커봐야 10000 을 넘지 않기 떄문에 배열 크기 를 10001 로 설정한다. 그리고 for문을 이용하여 모두 0 으로 초기화 시킨다. 그리고 중첩 for문을 이용하여 소수가 아닌 것들에 해당하는 배열을 0 에서 1 로 바꾸도록 하여 최종적으로 소수에 해당하는 배열만이 0 으로 남아있도록 한다. 그리고 마지막으로 해당 배열이 0 인지 1 인지 for문과 if문을 이용하여 판독하여 해당 범위내의 총합과 소수의 최솟값을 구하도록 하였다. loop_end 라는 변수에는 사용자가 입력한 범위의 끝부분(end 변수)의 제곱근 값을 넣음으로써 중첩 for문을 통해 소수를 걸러낼때 필요한 상한선을 설정하였다. 프로그래밍을 하는데에 수학이 절대 필요 없는 것이 아님을 보여주는 문제였다. (오늘 푼 달팽이 문제도 난 작년 수능 준비하면서 확률과 통계의 수열 단위에서 배운 ‘군’을 이용하여 풀었으니 프로그래밍에 수학은 꼭 필요해보인다.)

[에라토스테네스의 체] : https://namu.wiki/w/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98%20%EC%B2%B4

코드

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <math.h>
int main()
{
	int start=0, end=0,first=0,tot=0;
	scanf("%d", &start);
	scanf("%d", &end);
	int arr[10001];
	for (int l = start-1; l <= end; l++)
		arr[l] = 0;
	arr[0] = 1;
	int loop_end = sqrt(end);
	for (int i = 2; i <= loop_end; i++)
		for (int j = 2; i * j <= end; j++)
			arr[(i * j) - 1] = 1;
	for (int a = start; a < end+1; a++)
		if (arr[a - 1] == 0)
		{
			tot += a;
			if (first == 0)
				first = a;
		}
	if (tot == 0 && first == 0)
		printf("-1");
	else
		printf("%d\n%d", tot, first);
			
	return 0;
}