Square-free integer (제곱 인수가 없는 정수)

제곱 인수가 없는 정수는 1이 아닌 제곱수를 인수로 갖지 않는 (양의) 정수를 말합니다.

 

쉽게 말해서 소인수 분해를 했을 때, 같은 소수가 두 개 이상 나오지 않는 정수 입니다.

 

다음 숫자들이 Square-free integer 들 입니다.

 

1, 2, 3, 5, 6, 7, 10, 11, 13, 14, 15, 17, 19, 21, 22, 23, 26, 29, 30, 31, 33, 34, 35, 37, 38, 39, 41, 42, 43, 46, 47, 51, 53, 55, 57, 58, 59, 61, 62, 65, 66, 67, 69, 70, 71, 73, 74, 77, 78, 79, 82, 83, 85, 86, 87, 89, 91, 93, 94, 95, 97, 101, 102, 103, 105, 106, 107, 109, 110, 111, 113, ... (OEIS의 수열 A5117)

 

어떤 숫자가 Square-free number 인지 체크하는 코드 입니다.

def checkSquareFreeNumber(n):
    for i in range(2, round(n**0.5) + 1):
        if n % (i**2) == 0:
            return False
    return n

 

만약 특정 숫자까지 모든 값을 체크해야 한다면 아래와 같이 sieve 를 이용하는 것이 훨씬 효율적입니다.

def findSquareFreeNumbers(n):
    tArr = [True] * (n+1)
    tArr[0] = False
    tLimit = int(n**0.5) + 1
    for i in xrange(2, tLimit):
        ii = i**2
        for j in xrange(ii, n+1, ii):            
            tArr[j] = False
    tSFN = []
    for idx, value in enumerate(tArr):
        if (value):
            tSFN.append(idx)
    return tArr, tSFN