백준 2581 - 소수

문제 설명

에라토스테네스의 체를 사용하면 풀 수 있는 문제이다. 
기본적인 알고리즘은 쉽게 짰었는데 제대로된 예외처리를 못해서 5번 넘게 틀렸다....
2, 3, 5등은 소수인데 이 수들까지 소수가 아닌 것으로 인식을 되게 코드를 짜서 더 틀렸었다. 
작은 범위의 수들부터 정확히 따져보면서 코드를 짜야겠다. 

 

에라토스테네스의 체는 아래 URL에서 확인 가능하다.
https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전

 

#include <iostream>
#include <math.h>
using namespace std;
class Prime_Number
{
public :
	int number;
	bool prime=true;//true가 소수, false가 소수가 아니다. 
};
bool detec(int n)
{
	if (n <= 1)return false;
	for (int i = 2; i <= sqrt(n); i++) //keypoint 2 3 5 등은 true로 반환함
	{
		if(n%i==0)
		{
			return false;
		}
	}
	return true;
}


int main()
{
	int sum = 0;//소수의 합
	int min = 0;//가장 작은 소수
	int M, N, width;
	cin >> M >> N;
	width = N-M + 1;
	Prime_Number *arr = new Prime_Number[width];//배열 동적할당

	for (int i = 0; i < width; i++)//배열에 숫자 대입
	{
		arr[i].number = M;
		M++;
	}

	for (int j = 0; j < width; j++)
	{
		arr[j].prime = detec(arr[j].number);
	}

	for (int k = width-1; k >= 0; k--)
	{
		if (arr[k].prime)
		{
			min = arr[k].number;
			sum += arr[k].number;
		}
	}
	if(sum==0)
	{
		cout << -1 << '\n';
	}
	else {
		cout << sum << '\n' << min<<'\n';
	}
	return 0;
}