[알고리즘] 에라토스테네스의 체를 이용해 소수 구하기(JAVA)
소수(prime number) 1보다 큰 양의 정수 중에서 1과 자기 자신만으로 나누어 떨어지는 수를 말합니다. 에라토스테네스의 체 대표적인 소수 판별 알고리즘입니다. 1은 소수가 아니므로 2부터 소수를 구하려는 구간의 수를 모두 나열한 뒤 2의 배수부터 지워나가면 됩니다(2의 배수를 지운다면 자기 자신인 2는 지우지 않습니다) 1부터 50까지 소수 구하기 1. 2의 배수부터 지워나갑니다.(자기 자신은 지우지 않습니다) 2. 이미 지워진 숫자는 건너뛰고 3의 배수를 지웁니다.(자기 자신은 지우지 않습니다) 3. 위와 같은 방법을 반복해 지워나가면 소수만 남아있게 됩니다. 에라토스테네스의 체를 이용해 1부터 50까지의 소수 구하는 법을 JAVA 소스로 구현해보겠습니다. 1 2 3 4 5 6 7 8 9 10..
2021.09.24