에라토스테네스1 소수 판별 알고리즘과 에라토스테네스의 체 소수 판별 알고리즘 소수 판별 알고리즘은 시간복잡도에 따라 다르게 구현 가능하다. 시간 복잡도 O(N) 소수란, 약수가 1과 자기자신 뿐인 수를 말한다. 따라서 N이 소수인지 판별하는 가장 쉬운 방법은 2부터 N-1까지의 수로 나누어 떨어지는지 확인하고, 나누어 떨어진다면 소수가 아니라고 판단하는 것이다. bool isPrime(int N) { if (N < 2) return false; for (int i=2; i 2021. 11. 9. 이전 1 다음