thebjko   1년 전

rkddus96님의 코드를 보고 해석해보려고 하는데 도저히 이해가 안됩니다. 도움을 부탁드립니다.

dong5995   1년 전

소수 생성 알고리즘 중 순다람의 체를 이용한 코드입니다.

순다람의 체는 다음과 같이 동작합니다.

1 ~ N까지의 정수 리스트에 대해 1 <= i <= j이고 i + j + 2ij <= N인 모든 i + j + 2ij 수를 제거하고 남은 수에 대해 2를 곱하고 1을 더해서 2N + 2 이하의 홀수 소수 리스트를 도출합니다.

자세한 내용은 소수 생성 알고리즘(Prime-generating Algorithm) (tistory.com)의 순다람의 체 부분을 참고해주세요.

이걸 먼저 이해하시고 코드를 보시면, 

li = [False] + [True] * ((n - 1) // 2)  # 1 ~ (n-1)//2 까지의 정수리스트에 대해

for x in range(1, int(n ** .5 / 2 + 1)):   
  if li[x]:   
    li[2*x*(x+1)::x*2+1] = [False] * ((((n + 1) // 2) - x * x * 2) // (x * 2 + 1)) # 1 <= i <= j이고 i + j + 2ij <= N인 모든 i + j + 2ij 수를 제거하고

if m <= 2:
  print(2) #이 알고리즘은 홀수 소수 리스트만 도출하므로 2도 출력해주고

print('\n'.join([f'{x}' for x, val in zip(range(m+(m&1==0), n+1, 2), li[m//2:]) if val])) #남은 수에 대해 2를 곱하고 1을 더해서 2N + 2 이하의 홀수 소수 리스트를 도출합니다.

이런 식으로 된 코드입니다. 코드의 li[2*x*(x+1)::x*2+1]을 살펴보면, 1 <= i <= j이고 i + j + 2ij <= N인 모든 i + j + 2ij 에 대해 슬라이싱 해둔 것을 알 수 있습니다. i = j 일 때 i + j + 2ij = 2*i*(i+1) 이고 j 가 1씩 커질 때마다 i + j + 2ij 의 값은 i*2+1씩 커지기 때문에 위와 같은 코드가 나온 겁니다. 오른쪽 항은 [False] * (항의 개수)입니다.

마지막에 출력하는 부분은 그냥 어렵게 적어두었을 뿐이지, True 값이 들어있는 곳에 각각의 인덱스에 2를 곱하고 1을 더한 수를 zip을 이용해서 매칭한 다음 앞에것만 쭉 출력하는 코드입니다.

혹시 이해가 되지 않는 부분이 있다면 댓글주시면 설명드리겠습니다.

thebjko   1년 전

답변 감사합니다.

저도 이 코드와 씨름하다가 며칠 전에 제 나름대로 분석하긴 했습니다. https://velog.io/@thebjko/백준-1929.-소수-구하기-코드-분석

올려주신 링크도 읽어볼만한 글이네요. 감사합니다.

댓글을 작성하려면 로그인해야 합니다.