목록알고리즘/소수찾기 (1)

프로그래밍에 대한 고찰 및 생각

[1] 소수찾기 - 에라토스테네스의 체

소수의 정의 소수라 함은 자신보다 작은 두개의 자연수를 곱하여 만들수 없는 1보다 큰 자연수 이다. 예를 들어 2, 3, 5, 7 ,11 ... 등이 있다. 소수 구하기 소수를 구하는 대표적인 방법은 고대 그리스 수학자 에라토스테네스가 발견한 방법을 사용하는 것이다. 이 방법은 2부터 n까지의 자연수 수열에서 가장 앞에 있는 숫자가 소수가 되고 그 뒤로 그수의 배수들을 전부 지운다. 그리고 그 다음 남아있는 숫자가 소수가 되고 또 그 뒤로 그 수의 배수들을 전부 지운다 ... 이 과정을 반복하다보면 n까지의 소수들을 찾을 수 있다. 아래 자료를 보면 쉽게 이해가 될것이다. 이를 코드로 구현하는 것은 어렵지 않다. 아래는 파이썬으로 구현한 코드이다. n = int(input("")) arr = list(r..
알고리즘/소수찾기 2020. 2. 10. 17:47
이전 Prev 1 Next 다음