top of page
  • thebaleuncoding

에라토스테네스의 체가 뭘까?

약수가 1과 자기 자신뿐인 자연수를 소수라고 합니다.

예를 들어 2는 약수가 1과 자기 자신인 2뿐이고,

3도 약수가 1과 자기 자신인 3뿐이니까

2와 3은 소수입니다.

소수를 찾는 방법으로 그리스의 수학자이자 지리학자인 에라토스테네스가 생각해낸

'에라토스테네스의 체'라는 유명한 방법이 있습니다.

이 방법은 마치 체처럼 소수만을 걸러낸다고 하여 에라토스테네스의 체라고 부릅니다.

에라토스테네스의 체로 자연수 2부터 n까지의 수 중 소수를 구하는 방법은 다음과 같습니다.

1단계 : 2부터 n까지의 자연수로 이루어진 수열 DATA를 만듭니다.

DATA = (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 ,13, 14, 15, ..., n-1, n)

2단계 : 수열 DATA의 첫 번째 요소 p를 PRIME이라는 소수 열로 이동시킵니다.

DATA = (3, 4, 5, 6, 7, 8, 9, 10, 11, 12 ,13, 14, 15, ..., n-1, n)

PRIME = 2






#에라토스테네스의체 #에라토스테네스 #C언어로소수구하기

#에라토스테네스의체가뭘까?에 대해 더 알아보고 싶나요?

아래 링크로 이동하세요.

더 많은 내용 보기

조회수 24회댓글 0개

최근 게시물

전체 보기
bottom of page