목록소수 (1)

포시코딩

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

에라토스테네스의 체란? 2부터 주어진 숫자까지의 소수들을 찾는 방법으로 고대 그리스 수학자 에라토스테네스가 발견하였다. 원리는 2부터 주어진 숫자까지 모든 구간의 수를 나열한 후 2부터 시작해 발견되는 소수의 배수를 지워나가는 방식으로 소수를 찾는다. 자세한 방법은 위키백과에 나와있다. - [링크] 코드 1. 자신을 포함 안시키는 경우 def prime_list(n): # 에라토스테네스의 체 초기화: n개 요소에 True 설정(소수로 간주) sieve = [True] * n # n의 최대 약수가 sqrt(n) 이하이므로 i=sqrt(n)까지 검사 m = int(n ** 0.5) for i in range(2, m + 1): if sieve[i] == True: # i가 소수인 경우 for j in ran..
자료구조알고리즘/이론 2023. 4. 16. 05:39
이전 Prev 1 Next 다음