narita_jin   2년 전

안풀려서 다른분들꺼 풀이 보고 있는데 이해가 가지 않는 부분이 있어서요

for odd_num in range(3, int(math.sqrt(246_912))+1, 2): # 3부터 최대값의 제곱근까지 홀수만
nums -= {i for i in range(2 * odd_num, 246_913, odd_num) if i in nums}
# 홀수의 배수로 이루어진 집합을 생성해서 빼줌

소수의 집합을 구하는 과정인데

왜 첫줄for문에서 3부터 최대값의 제곱근까지 홀수만 돌리는지?(소수가 2를 제외하고 전부 홀수 인건 알겠는데 왜 246912번까지가 아닌 246912의 제곱근까지만 돌리는지 이해가 가지않네요)

두번째 줄 "홀수의 배수로 이루어진 집합을 생성해서 빼줌" 도 이해가 가질 않네요 ㅠㅠ


쉽게 설명해 주시면 감사하겠습니다~

dbshin59   2년 전

왜 첫줄for문에서 3부터 최대값의 제곱근까지 홀수만 돌리는지?(소수가 2를 제외하고 전부 홀수 인건 알겠는데 왜 246912번까지가 아닌 246912의 제곱근까지만 돌리는지 이해가 가지않네요)

에 대한 답은, 2 부터 n의 제곱근까지의 모든 소수를 구하고, 그들의 배수를 전체 배열에서 빼면 배열의 모든 수가 소수가 됩니다.

여기에서 핵심은, 어떤 수가 합성수라면, 무조건 2와 어떤 수의 제곱근 사이에서 나누어지는 수가 있다는 것입니다.

(증명)
n 을 합성수라 하자. 그러면 n=ab 로 표현할 때, 1
만약 a,b 가 둘 다 n의 제곱근보다 크다면 [ a, b > sqrt(n) ]
ab > n 가 되어 n = ab 와 모순이다. 따라서 a,b 중 적어도 하나는 n의 제곱근보다 작거나 같다.
,b

예를 들어, 수 35는 5와 7의 배수입니다. 그렇다면, 이 수가 소수인지 판별하기 위해서는 7 까지 탐색할 필요 없이 5까지만 탐색하면 됩니다.

핵심은, 합성수는 어떤 둘보다 더 큰 소수의 곱으로 이루어져 있고, 만일 한 인수가 크다면, 나머지 인수는 그만큼 작게 된다.

두 인수 모두가 가장 큰 (min(x, y) 의 값이 가장 큰) 값은 두 수가 같은 제곱근이 한계점이다. 따라서 2와 n의 제곱근까지의 모든 소수를 구하고, 그의 배수를 원래 리스트에서 제거하면, 모두 소수가 된다 는 것입니다.

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