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

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

1978번: 소수 찾기

코드

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

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[1001];
	memset(isPrime, true, sizeof(isPrime));
	isPrime[1] = 0; // 1 is not a prime number.
	
	for(int i=2; i<=1000; i++){
		if(isPrime[i] == true && check_Prime(i)){
			for(int j=i * 2; j < 1001; j += i){
				isPrime[j] = 0;
			}
		}
	}
	
	int t, n, answer = 0;
	cin >> t;
	
	for(int i=0; i<t; i++){
		cin >> n;
		if(isPrime[n]) answer += 1;
	}
	
	cout << answer;
}

 

풀이

시간 제한은 2초로 꽤 넉넉하며, 주어지는 수는 100개에 모두 1000이하의 자연수이기때문에

최적의 소수 찾기 방법보다는 '소수를 판별한다'에 중점을 두고 풀어도 괜찮은 문제이지만

지난 백준 단계별 문제 풀이 경험상 어차피 소수를 찾는 문제가 몇 개는 더 나온다는것을 알기 때문에

그냥 처음부터 '에라토스테네스의 체'를 사용해서 풀었다.

 

길이가 1001인 Boolean 배열을 하나 생성해주고. (index 0부터 시작하므로 0~ 1000까지, 0은 있지만 없는셈)

배열안의 값이 True 라면 Prime Number,

False라면 Prime Number가 아니라는 전제를 걸어놓고 코드를 짰다.

 

우선 1000이하의 모든 자연수가 Prime Number 라고 memset, 초기화를 해 준다.

이후, 해당 수가 실제로 Prime Number라면, 그 수의 1000 이하 배수들은 Prime Number가 아니라고 설정.

그렇게 1000 이하의 모든 자연수들을 에라토스테네스의 체를 사용해서 미리 소수 판별을 해 주고.

 

입력 값을 배열에 대입해서 답을 출력해주었다.

 

물론 에라토스테네스의 체를 사용하지 않고, 단순히 Prime Number를 판별하는 함수인.

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;
	}
}

위의 부분만 충분히 잘 활용해도 아마 풀 수있을것이다. 아마도...

 

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

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

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

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

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

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