소수 찾기 (feat. 백준, 1978번)

소수 찾기
https://www.acmicpc.net/problem/1978

1978번: 소수 찾기

반응형

// woohyeon.kim
// https://www.acmicpc.net/problem/1978
#include <iostream>
#include <cmath>
using namespace std;
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
	register int N, ans = 0, check[1001] = { 0 };
	check[0] = check[1] = 1;
	for (int i = 2; i <= sqrt(1000); i++) {
		if (check[i] == 0) {
			for (int j = i + i; j <= 1000; j += i) {
				check[j] = 1;
			}
		}
	}
	cin >> N;
	for (register int i = 1, v; i <= N; ++i) {
		cin >> v;
		if (!check[v])		++ans;
	}
	cout << ans << endl;
	return 0;
}
// *&)*@*

소수를 구하는 방법은 여러가지가 있습니다.

2부터 구하려는 값까지 for문을 돌며 나머지를 확인하는 방법도 있구요.

2부터 구하려는 값의 루트까지 for문을 돌며 나머지를 확인하는 방법도 있구요.

하지만 가장 빠른 (빅-오 기준) 소수 구하는 방법은 "에라토스테네스의 체" 라는 방법으로 구하는 방식입니다.

관련 내용은 아래 위키를 참고하시면 좋겠습니다.

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