Algorithm (알고리즘)
Algorithm in A..Z - 에라토스테네스의 체
강태종
2020. 11. 28. 20:14
개념
소수를 판별하는 알고리즘
작동원리
1. 2부터 시작한다.
2. 방문하지 않은 숫자이면 그 숫자의 배수를 전부 체크한다.
3. 체크되지 않은 숫자는 소수이다.
시간복잠도
O(NloglogN)
문제
1978 소수찾기
1978번: 소수 찾기
첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다.
www.acmicpc.net
코드
#include <iostream>
#include <vector>
using namespace std;
constexpr int MAX = 1000;
int main() {
vector<bool> isPrime(MAX, true);
isPrime[0] = isPrime[1] = false;
for (int i = 2; i*i <= MAX; ++i) {
if (isPrime[i]) {
for (int j = i*i; j <= MAX; j += i) {
isPrime[j] = false;
}
}
}
int n;
cin >> n;
int answer = 0;
while (n--) {
int num;
cin >> num;
answer += isPrime[num];
}
cout << answer << "\n";
}