[알고리즘] 소수(Prime Number) 구하기 - Java

목차 소수 소수 구하기 에라토스테네스의 체(Sieve of Eratosthenes) 소수 소수 (prime number) 는 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수 입니다. 1과 그 수 자신 이외의 자연수로는 나눌 수 없는 자연수로 정의됩니다. 예를 들어, 7은 \(1 \times 7 \), \(7 \times 1\) 로 7, 1 만 약수로 가지기 때문에 소수입니다. 그러나 6은 \( 2 \times 3 \) 이라는 자신보다 작은 두 숫자의 곱 으로 나타낼 수 있기 때문에 소수가 아닙니다. 이렇듯 1보다 큰 자연수 중 소수가 아닌 것은 합성수 라고 합니다. 소수 구하기 주어진 수가 소수인지 판별하는 문제는 가장 기초적인 문제입니다. 가장 간단한 방법으로는 2부터 n-1 까지의 모든 수..

원문링크 : [알고리즘] 소수(Prime Number) 구하기 - Java