파이썬, 소수 구하는 특이한 방법

파이썬, 소수 구하는 특이한 방법 

 

글. 수알치 오상문 

 

6의 배수에서 -1. +1인 숫자인지 확인하는 구별법이다. 
5 이상의 소수들은 6의 배수에서 -1, +1인 숫자들이 많은 것을 알 수 있다. 
이 규칙을 이용하여 소수를 판별하는 파이썬 코드는 다음과 같다.  

 

def isPrime(num):
    y = 2;
 
    if num < 2:             # 1 이하는 소수 아님
        return 0
    if num==2 or num==3:    # 2, 3은 소수
        return 1  
    if num%2==0 or num%3==0:# 2, 3의 배수는 소수 아님
        return 0 
    
    x = int(num**0.5);      # 제곱근 이용

    i = 5
    while i <= x:
        i += y
        y = 6 - y
        if num%i == 0:
            return 0;

    return 1;

print(isPrime(31))   # 1