목록Sieve of Eratosthenes (1)

안경잡이 구루루

[ Algorithm ] 에라토스테네스의 체 ( Python )( 소수를 구하는 방법)

고대 수학자 에라토스테네스가 만들어 낸 소수를 찾는 방법이다. 이 방법은 체로 치듯이 수를 걸러낸다고 해서 '에라토스테네스의 체' 라고 불린다.소수를 구하는 방법은 여러가지가 존재하지만 이 방식을 이용하면 보다 효과적으로 소수를 빠르게 구할 수 있다. 먼저 나무위키, 위키백과의 그림을 참고하자. 간단히 위 그림을 설명하자면 1과, 2, 3, 5, 7의 배수인 수들을 모두 제거하면 소수만 남게 된다.어떻게 이런 방식을 사용할 수 있을까? 라는 질문이 나올 수 있다. 우선 소수에 대해 알아 볼 필요가 있다.소수란 1과 자기 자신 이외에 약수를 가지는 합성수이다. 그렇다면 여기서 위의 원리를 유추할 수 있다.즉 1과 자기 자신 이외에 약수를 가지게 되는 ..
파이썬(Python)/알고리즘, 자료구조 2020. 6. 23. 19:23
이전 Prev 1 Next 다음