[C++][에라토스테네스의 체] 백준 1978번 소수 찾기 :: seoftware

문제

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

1978번: 소수 찾기

에라토스테네스의 체 참고글

2020/03/03 - [IT/코딩테스트] - [C++][백준 4673][에라토스테네스의 체] 셀프 넘버 :: seoftware

[C++][백준 4673][에라토스테네스의 체] 셀프 넘버 :: seoftware

소스코드

#include <iostream>
#include <cmath>
using namespace std;
int N;
bool isPrime(int x) {
	if (x == 1) return false;
	else if (x == 2) return true;
	else {
		for (int i = 2; i <= sqrt(x); i++) {
			for (int j = i + i; j <= x; j += i) {
				if (j == x) return false;
			}
		}
		return true;
	}
}

int main(void) {
	cin >> N;
	int cnt = 0;
	for (int i = 0; i < N; i++) {
		int input;
		cin >> input;
		if (isPrime(input)) cnt++;
	}
	cout << cnt << endl;
}

isPrime 함수에서 에라토스테네스 체를 사용했다. 배열을 따로 만들지 않고 j == x 이면 소수가 아니라고 리턴하였다. j는 i의 배수이므로 만약 x가 소수인 경우에는 j == x가 될 수가 없기 때문이다.