백준 2581번: 소수 [C++]

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

2581번: 소수

코드

#include <iostream>
#include <string.h>
#include <cmath>
using namespace std;

// Parameter로 주어진 num가 Prime Number인지 확인하여 Bool Type Return  
bool check_Prime(int num){
	if(num == 2 || num == 3) return 1;
	else{
		for(int i=2; i<=sqrt(num); i++){
			if(num % i == 0) return 0;
		}
		return 1;
	}
}


int main() {
	bool isPrime[10001];
	memset(isPrime, true, sizeof(isPrime));
	isPrime[1] = 0; // 1 is not a prime number.
	
	for(int i=2; i<=10000; i++){
		if(isPrime[i] == true && check_Prime(i)){
			for(int j=i * 2; j <= 10000; j += i){
				isPrime[j] = 0;
			}
		}
	}
	
	int M, N, sum = 0, min = 10001;
	cin >> M >> N;
	for(M; M <= N; M++){
		if(isPrime[M]) 
		{
			sum += M;
			if(min == 10001) min = M;
		}
	}
	
	if(sum == 0) cout << -1;
	else cout << sum << endl << min;
	return 0;
}

 

풀이

이전 1978번 : 소수찾기 코드를 재탕해서 풀었다. 애초에 그러려고 처음부터 그렇게 짰으니까.

https://wonsang98.tistory.com/185

백준 1978번: 소수 찾기 [C++]

1978번 문제와 달라진거라고는 크게 보면 소수를 찾아야하는 자연수의 범위?

물론 세세하게 보면 1978번은 주어진 자연수들 중 소수가 몇개인지였고, 이 문제는 범위내에 소수의 합과, 가장 작은 소수를 출력하는거지만, 결론적으로 범위내에서 소수를 찾는것이라는건 변함이 없기때문에

1978번이 1000이하의 자연수였다면, 이 문제에서는 배열을 10001까지 만들어준 후, 에라토스테네스의 체를 자연수 10000까지 사용하여 미리 소수를 판별해놓고 그 배열에서 값을 뽑아서 호출하면 되는 문제였다.

백준 단계별로 풀어보기 기본수학2에는 소수 문제가 총 3개가 있는데, 마지막으로 1929번 소수 구하기에서도 재탕을하면서 소수문제풀이를 마무리 지어보도록 하겠다.

 

위 풀이는 에라토스테네스를 잘못 사용한 풀이입니다.

실제 에라토스테네스의 체를 사용하면 소수판별 함수를 따로 기용할 필요가 없습니다.

풀이 당시 착각으로 인해 발생한 비효율적인 코드입니다.

실제 에라토스테네스의 체를 사용한 코드는 아래 링크에서 확인 바랍니다.

옳게 된 에라토스테네스의 체 코드

백준 1929번: 소수 구하기 [C++]