이 프라임 테스트는 왜 작동합니까?

Question

숫자가 소수인지 여부를 테스트하기 위해이 Python 함수를 찾았습니다. 그러나 알고리즘이 어떻게 작동하는지 알 수는 없습니다.

def isprime(n): 
    """Returns True if n is prime""" 
    if n == 2: return True 
    if n == 3: return True 
    if n % 2 == 0: return False 
    if n % 3 == 0: return False 

    i = 5 
    w = 2 
    while i * i <= n: 
     if n % i == 0: 
     return False 

     i += w 
     w = 6 - w 

    return True 

Answer 1

의 함수의 코드의 처음 네 줄 시작하자 : n가 제 2 또는 제 3 같으면

def isprime(n): 
    if n == 2: return True 
    if n == 3: return True 
    if n % 2 == 0: return False 
    if n % 3 == 0: return False 

기능 시험보고. 두 숫자가 모두 소수이기 때문에 n과 같으면 True을 반환합니다.

다음 함수는 n이 2 또는 3으로 나눌 수 있는지 확인하고 둘 중 하나가 참이면 False을 반환합니다. 이것은 2를 초과하는 모든 숫자의 절반이 소수가 아니기 때문에 매우 많은 양의 사례를 제거합니다. 2로 나눌 수 있습니다. 동일한 이유가 3으로 나누기 테스트에도 적용됩니다. 또한 많은 경우가 제거됩니다.

함수의 난이도 부분은 몇 라인이다

i = 5 
w = 2 
while i * i <= n: 
    if n % i == 0: 
     return False 

    i += w 
    w = 6 - w 

return True 

먼저 i (또는 인덱스) (5) (2, 3)으로 설정되어 이미 테스트되었으며, 4 n % 2 테스트되었습니다 . 따라서 5 시부 터 시작하는 것이 좋습니다.

다음으로 w은 2로 설정됩니다. w은 "증분 자"인 것처럼 보입니다. 지금까지,이 함수는 모든 짝수 (n % 2)에 대해 시험했다 그래서 2

함수가 조건 i * i <= n와 while 루프로 진입하여 빠르게 증가 할 것이다. 이 테스트는 every composite number has a proper factor less than or equal to its square root이기 때문에 사용됩니다. 숫자가 중복되므로 제곱근 이후의 숫자를 테스트하는 것은 의미가 없습니다. i로 나누어 n 경우 while 루프에서

은 다음 프라임하지 않고 함수는 False를 반환합니다. 그렇지 않은 경우 i은 "증분 자" w에 의해 증가되며, 이는 다시 더 빠릅니다.

아마 함수의 가장 까다로운 부분은 두 번째 - 마지막 줄에 있습니다 : w = 6 - w. 이로 인해 "증분 장치"w은 각 통과 루프마다 값 2와 4 사이를 토글합니다. w이 4 인 경우 우리는 3으로 나눌 수를 우회합니다.이 함수는 이미 2와 3 모두로 나눗셈을 테스트했기 때문에 2에 남아있는 것보다 빠릅니다.

마지막으로이 함수는 True을 반환합니다. 함수가 n이 무언가로 나눌 수있는 경우를 발견하지 못하면 소수이어야합니다.

Answer 2

2와 3을 제외한 모든 소수는 (6 * n) +1 또는 (6 * n) -1을 사용하여 나타낼 수 있습니다. 여기서 n은 0에서 무한대까지입니다. 이 프로그램은이 아이디어에 따라 작동합니다. 이 라인을 사용하여 그런 다음 우리가 3 이외의 소수 강판으로 나눌 수있는 수를 확인해야

if n % 2 == 0: return False 
if n % 3 == 0: return False 

2 또는 3 수를 나눌 수 확인.

i = 5 
w = 2 
while i * i <= n: 
    if n % i == 0: 
     return False 

    i += w 
    w = 6 - w 

다음 소수 제 세트의 모든 번호 (6 * 않음) +1 또는 (6 * 않음)을 얻기 위해서는 -1 대안의 값을 변경 전 항 때문에 초기 값 설정 인 w (2,4). 그리고이 스 니펫은 숫자의 제곱근을 검사하는 데 사용됩니다.

while i * i <= n: 

이 코드는 set (6 * n) +1 또는 (6 * n) -1의 일부 소수가 아니기 때문에 효율적이지 않습니다.