1740 : 소수

문제

자연수 M과 N이 주어질 때 M이상 N이하의 자연수 중 소수인 것을 모두 골라 이들 소수의 합과 최소값을 찾는 프로그램을 작성하시오.

 

예를 들어 M=60, N=100이 경우 60이상 100이하의 자연수 중 소수는 61, 67, 71, 73, 79, 83, 89, 97 총 8개가 있으므로, 

이들 소수의 합은 620이고, 최소값은 61이 된다.

 

입력형식

입력의 첫째 줄에 M이, 둘째 줄에 N이 주어진다.

M과 N은 10,000이하의 자연수이며, M은 N보다 같거나 작다.

 

출력형식

M이상 N이하의 자연수 중 소수인 것을 모두 찾아 첫째 줄에 그 합을, 둘째 줄에 그 중 최소값을 출력한다.

단, M이상 N이하의 자연수 중 소수가 없을 경우는 첫째 줄에 -1을 출력한다.

 

<코드>

#include <stdio.h>
#include <math.h>

//return 0: prime return 1: composite
int check_prime(int N)
{
	int sq, count=0;
	
	if(N == 1)
		return 1;
	
	sq = (int)sqrt(N);

	for (int i = 2; i <= sq; i++)
	{
		if (!(N%i))
		{
			count++;
		}
		
		if(count>0)
			break;
	}
	
	return count;
}

int main()
{
	int x, y, prime;
	int sum=0, first=0;
	
	scanf("%d %d", &x, &y);
	
	for(int i=x; i<=y; i++)
	{
		prime = check_prime(i);
		if(!prime)
		{
			if(!first)
				first = i;
			sum+=i;
		}
	}
	
	if(sum)
		printf("%d\n%d\n", sum, first);
	else
		printf("-1\n");
	
	return 0;
}