---

개요

파이썬으로 소수 구하기

---

📌 소수

1과 그 수 자신 이외의 자연수로는 나눌 수 없는 자연수

---

📌 파이썬으로 소수 구하기

n=120
def isPrime(a):         # 소수를 구하는 함수 정의
  if(a<2):              # 소수는 1보다 크기 때문에 2보다 작으면 False 반환
    return False
  for i in range(2,a):  # 2부터 a-1까지 a가 i로 나누어 떨어지면 소수가 아니므로 False 반환
    if(a%i==0):
      return False 
  return True           # 2보다 작지 않고 자신 외에 나누어 떨어지는 숫자가 없다면 True 반환
primelist = []          # 소수를 담을 리스트 생성
for i in range(n+1):    # 0부터 n (=100) 까지 반복
  if(isPrime(i)):       # isPrime 함수에 i를 넣어 True (소수) 이면
    primelist.append(i) # primelist에 i를 추가
print(primelist)

---

📌 에라토스테네스의 체

수학에서 에라토스테네스의 체는 소수를 찾는 빠르고 쉬운 방법인데, 이를 파이썬 코드로 구현이 가능하다.

+) 에라토스테네스는 고대 그리스 수학자이며, 소수를 찾는 빠르고 쉬운 방법을 발견하였다.

• 알고리즘 설명
  2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. (회색)
  2는 소수이므로 오른쪽에 2를 쓴다. (빨간색)
  자기 자신을 제외한 2의 배수를 모두 지운다.
  남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. (초록색)
  자기 자신을 제외한 3의 배수를 모두 지운다.
  남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. (파란색)
  자기 자신을 제외한 5의 배수를 모두 지운다.
  남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다. (노란색)
  자기 자신을 제외한 7의 배수를 모두 지운다.
  위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다. (보라색)
  

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 range(i+i, n, i): # i이후 i의 배수들을 False 판정
                sieve[j] = False
    # 소수 목록 산출
    return [i for i in range(2, n) if sieve[i] == True]
print(prime_list(120))

---

이미지 출처 및 참고