목록Java/알고리즘 (1)
MyPrograming
에라토스테네스의 체 (소수찾기)
1. 소수(prime number) 소수란, 1보다 큰 자연수 중에서 1과 자기 자신만을 약수로 갖는 자연수를 의미한다. ex) 7 -> 1,7 9 -> 1,3,9 이처럼 소수는 2개의 약수만을 갖고, 그 약수는 1과 자신 뿐이다. 만약 이 외의 약수를 갖고있는 자연수라면 소수라고 할 수 없으며 합성수라고 부르게 된다. 2. 에라토스테네스의 체 에라토스테네스의 체는 가장 대표적인 소수(prime number) 판별 알고리즘이다. 진행 방법은 아래와 같다. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 2는 소수이므로 오른쪽에 2를 쓴다. 자기 자신을 제외한 2의 배수를 모두 지운다. 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. 자기 자신을 제외한 3의 배수를 모두 지운다. 남아있는..
Java/알고리즘
2021. 9. 15. 18:01