Dot Algo∙ DS/알고리즘 개념
2021. 6. 12.
[알고리즘] 소수(Prime Number) 구하기 - 에라토스테네스의 체 (Java)
소수 소수(prime number)는 정수론의 가장 중요한 연구 대상 중 하나로, 양의 약수가(1보다 큰 자연수) 1과 자기 자신만을 약수로 가지는 수를 의미한다. 소수의 반대말로, 세 개 이상의 양의 약수를 갖는 자연수를 합성수라고 부른다. 예를 들어, 5는 1×5 또는 5×1로 수를 곱한 결과를 적는 유일한 방법이 그 수 자신을 포함하기 때문에 5는 소수이다. 그러나 6은 자신보다 작은 두 숫자(2×3)의 곱이므로 소수가 아닌데, 이렇듯 1보다 큰 자연수 중 소수가 아닌 것은 합성수라고 한다. 1과 그 수 자신 이외의 자연수로는 나눌 수 없는 자연수로 정의하기도 한다. 소수 구하기 주어진 수가 소수인지 판별하는 문제는 소수에 관련된 가장 기초적인 문제이다. 주어진 수 n이 소수인지를 판단하는 가장 단..
![[알고리즘] 소수(Prime Number) 구하기 - 에라토스테네스의 체 (Java)](http://i1.daumcdn.net/thumb/C450x300/?fname=https://blog.kakaocdn.net/dn/baeHRU/btq650s4ps8/U4cmsNgQjEQHDqZykxtwN1/img.png)