1223

에라토스테네스의 체 소수를 판별하는 알고리즘 단일 숫자의 소수 여부 확인 어떤 수의 소수 여부를 확인할 때는, 특정한 숫자의 제곱근까지만 약수의 여부를 검증하면 O(N^1/2)의 시간 복잡도로 빠르게 구할 수 있다. 에라토스테네스의 체 원리 배열을 생성하고 초기화 2부터 시작해서 특정 수의 배수에 해당하는 수를 모두 지운다. (자기 자신은 지우지 않고, 이미 지워진 수는 건너뛴다. 2부터 시작하여 남아있는 수를 모두 출력 public class PrimeNumber2 { static int max = 999; static boolean[] prime; public static void main(String[] args) { prime = new boolean[max + 1]; primeNum(); for..