Chef.Yeon
Code Cook
Chef.Yeon
전체 방문자
오늘
어제
  • 분류 전체보기 (230)
    • 게임 개발 (1)
      • Unity (1)
    • Android (27)
      • Kotlin (19)
      • 우아한테크코스 5기 (4)
    • Language (11)
      • 파이썬 (3)
      • Java (7)
    • DB (2)
      • SQL (16)
    • Spring (25)
    • 코딩테스트 (56)
    • Git (1)
    • TIL (85)
    • DevOps (6)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • 프로그래머스
  • grafana
  • kibana
  • 내림차순
  • elasticsearch
  • Docker
  • 코틀린
  • 레포지토리
  • SQL
  • java
  • 파이썬
  • rsocket
  • 코딩테스트
  • 백준
  • 에라토스테네스의 체
  • Wil
  • 문자열
  • 우아한테크코스
  • spring
  • ec2
  • 코틀린 인 액션
  • 안드로이드
  • MariaDB
  • webflux
  • 프리코스
  • kotlin
  • Android
  • til
  • enum
  • 다이나믹 프로그래밍

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
Chef.Yeon

Code Cook

Language/파이썬

[파이썬] 소수 판별 '에라토스테네스의 체'

2022. 10. 20. 14:52
728x90

에라토스테네스의 체

 

1. 소수를 구하고자 하는 범위를 2부터 나열

 

2~n 사이의 소수를 구하고자 할 때 다음과 같이 나열합니다.

0과 1은 False로 두고, 2~n-1개까지 True로 둡니다. 

a = [False,False] + [True]*(n-1)

 

2. 2부터 나열한 수까지 반복하며 배수 지우기

 

  • 2부터 n+1까지 반복문을 돌리고 a의 i 번째 인덱스가 True 이면 primes 리스트에 추가합니다.
  • 만약 n=10, i= 2이면, 현재 a[2]는 True이므로 primes에 2를 추가하고 2의 배수인 4,8이 False가 됩니다.
  • 3도 primes에 추가되고 배수인 6,9가 False가 됩니다.
  • 4는 2의 배수를 지우는 단계에서 False가 되었으므로 if문을 통과하지 못합니다.
  • 5는 True 이므로 primes에 추가되고 배수인 10이 False가 됩니다.
  • 10까지 위 과정을 반복합니다.
n=10
a = [False,False] + [True]*(n-1)
primes=[]

for i in range(2,n+1):
  if a[i]:
    primes.append(i)
    for j in range(2*i, n+1, i):
        a[j] = False
print(primes)

결국 primes = [2,3,5,7] 이 됩니다.

 

[파이썬/코딩테스트] - [프로그래머스/파이썬] 소수 찾기

 

[프로그래머스/파이썬] 소수 찾기

문제 설명 1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요. 소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다. (1은 소수가 아닙니다.) 제한 조

yeon-dev.tistory.com

 

728x90

'Language > 파이썬' 카테고리의 다른 글

[Python] VSCode-ModuleNotFoundError: No module named 'bs4' 오류 해결  (0) 2023.01.20
[파이썬] 최대공약수와 최소공배수  (0) 2022.09.25
    'Language/파이썬' 카테고리의 다른 글
    • [Python] VSCode-ModuleNotFoundError: No module named 'bs4' 오류 해결
    • [파이썬] 최대공약수와 최소공배수
    Chef.Yeon
    Chef.Yeon
    보기 좋고 깔끔한 코드를 요리하기 위해 노력하고 있습니다.

    티스토리툴바