[종만북] 약수의 개수 구하기 / 정수론 / Python 파이썬

[종만북] 약수의 개수 구하기 / 정수론 / Python 파이썬

[종만북] 약수의 개수 구하기 / 정수론 / Python 파이썬

1. 에라토스테네스의 체를 이용

• 에라토스테네스의 체를 이용하여 가장작은 소인수를 구하고 이를 이용하여 약수의 개수를 구함

# 1천만 이하의 모든 수의 약수의 개수를 계산하는 알고리즘

Max = 10000000

# 가장 작은 소인수
minFactor = [x for x in range(Max+1)]
minFactor[0] = 0
minFactor[1] = 1

sqrtn = int(Max ** 0.5)

for i in range(2, sqrtn+1):
    if minFactor[i] == i:
        for j in range(i*i, Max+1, i):
            if minFactor[j] == j:
                minFactor[j] = i


# minFactorPower[i] = i 의 소인수 분해에는 minFactor[i]의 몇승이 포함되는지
minFactorPower = [0] * (Max + 1)

# factors[i] = i 가 가진 약수의 개수
factors = [0] * (Max + 1)


def getFactorsSmart():
    global Max, minFactor, minFactorPower, factors

    # 1의 약수는 1개
    factors[1] = 1

    for i in range(2, Max+1):
        # 소수인 경우
        if minFactor[i] == i:
            # i ** 1 승
            minFactorPower[i] = 1
            # 소수 [1, i] -> 2개
            factors[i] = 2
        else:
            # i 의 가장작은 소인수
            p = minFactor[i]

            # 가작 작은 소인수로 나눈 수
            m = i // p

            # i 의 가장작은 소인수와 m 의 가장작은 소인수가 같지 않음
            if p != minFactor[m]:
                minFactorPower[i] = 1

            # i 의 가장작은 소인수와 m 의 가장작은 소인수가 같음
            # i의 가장작은 소인수 = m 의 가장작은 소인수 + 1 승
            else:
                minFactorPower[i] = minFactorPower[m] + 1

            a = minFactorPower[i]

            # m 의 가장작은 소인수의 개수를 대체(+1)하여 기록
            factors[i] = (factors[m]//a) * (a+1)


getFactorsSmart()

 

 

2. 브루트포스

• 어떤 수의 배수를 찾는 방법으로 약수의 개수를 구함

# 1천만 이하의 모든 수의 약수의 개수를 계산하는 알고리즘
# 에라토스테네스의 체를 사용하지 않고, brute force 로 해결


Max = 10000000

factors = [0] * (Max + 1)


def getFactorsBrute():
    global factors
    for i in range(1, Max+1):
        for j in range(i, Max+1, i):
            factors[j] += 1


getFactorsBrute()
print(factors[:10])