[백준-1978]소수 찾기(C++)

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

1978번: 소수 찾기

입력받은 수 중에서 소수의 개수를 찾는 간단한 문제입니다.

예전에 프로그래머스에서 풀어봤는데 그 때 막코딩으로 풀었다가 계속 시간초과 났던게 생각나네요ㅜㅜ

 

우리가 수학시간에 배워서 알고있던 소수의 정의로 푸는 것 보다 좀더 빠르게 구현할 수 있는 소수찾는 알고리즘이 있습니다.

 

소수 찾는 알고리즘

소수 배열이 있다고 생각해봅시다.

소수 배열에는 일단 확실히 소수인 2만 들어가있습니다.

2부터 시작해서 3,4,5,6,7,8,9... 이 수들이 소수인지 판별해볼건데요 방법은 꽤 간단합니다.

 

소수 배열의 숫자로 이 수가 나누어 지는가?

true -> 소수 아님

false -> 소수임

 

+이 때 지금 판별 중인 숫자가 소수배열의 숫자보다 커야합니다!

(소수 배열 11로 숫자 8을 판별하진 못하죠, 소수<판별하는 수)

 

 

예) 1~10에서 소수를 찾는 과정

소수 ={ 2 }

1 은 2보다 작으므로 통과

2는 소수

3은 2로 나누어 떨어지지 않으므로 소수

 

소수 = { 2, 3 }

4는 2로 나누어 떨어지므로 소수아님

5는 2,3으로 나누어 떨어지지 않으므로 소수

 

소수 = { 2, 3, 5 }

6은 2로 나누어 떨어지므로 소수아님

7은 2,3,5로 나누어 떨어지지 않으므로 소수

 

소수 = { 2, 3, 5, 7 }

8은 2로 나누어 떨어지므로 소수아님

9는 3으로 나누어 떨어지므로 소수아님

10은 2로 나누어 떨어지므로 소수 아님

 

1~10에서 소수 배열 { 2, 3, 5, 7 }을 찾았습니다.

 

소스 코드(C++)

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
	int N;
	vector <int> v; //입력 값
	vector <int> prime; //소수 배열
	int ans = 0; //출력 값(소수 개수)
	bool isPrime = true; //소수판별

	cin >> N; //테스트케이스 입력

	for (int i = 0; i < N; i++) { //입력
		int a, b;
		cin >> a;
		v.push_back(a);
	}
	sort(v.begin(), v.end()); //정렬

	prime.push_back(2); //소수 배열에 2추가 하고 시작

	//입력받은 최댓값까지의 소수 배열 만들기
	for (int i = 3; i <= v[v.size()-1]; i++) { //입력 값의 마지막 원소(최댓값)까지 반복
		isPrime = true;
		for (int j = 0; j < prime.size(); j++) { //소수 배열 크기 만큼 반복

			if (i>=prime[j]&&i % prime[j] == 0) { //소수 배열 수보다 크면서 나누어 떨어지면 소수 아님
				isPrime = false;
				break;
			}
		}
		if (isPrime == true) { //위쪽 if문을 모두 통과 시 소수임
			prime.push_back(i); //소수 배열에 추가
		}
	}

	//위에서 만든 소수 배열과 입력 값 비교해서 소수 판별
	for (int i = 0; i < v.size(); i++) {
		for(int j = 0;j<prime.size();j++)
			if (v[i] == prime[j]) {
				ans += 1;
				break;
			}
	}
	cout << ans; //입력값 중 소수 개수 출력
}

처음에는 소수 배열을 늘려가면서, 입력값과 비교하여 바로바로 판별할려고 했는데 코드가 복잡해보일 거같아서

그냥 입력값의 최댓값까지 소수를 찾아둔 뒤, 소수 배열과 입력값의 일치여부로 소수 판별 했습니다.

동적계획법 비스무리하게^-^

 

궁금한거 질문주세요~

 

 

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

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

그림 참고하시면 이해하는데 도움 되실거에요!