알고리즘 이론 - 정수론

정수론

• 모듈러의 성질
• 소수 판정
• 약수 구하기
• 소인수 분해
• 유클리드 호재법
• 에라토스테네스의 체
• 빠른 거듭제곱

(a+b) % c == (a%c + b%c) % c
(a*b) % c == (a%c * b%c) % c
(a-b) % c == (a%c - b%c + c) % c #음수가 되면 +c를 해줘야함.
(a+b) % c == (a//c - b//c) % c #페르마소 정리, 수학적으로는 가능. 코딩에선 안됨.

1. 소수 판정

• n의 제한이 10^12정도로 나옴.

#소수 판정
#소수면 YES, 아니면 NO
# 12의 약수
# 1 2 3 4 6 12

# 1 12 약수는 쌍으로 존재
# 2 6
# 3 4


# 왼쪽 <= 오른쪽 따라서 왼쪽 수는 모두 루트n 이하.
# 1~루트n까지 약수가 정확히 하나인지 구한다.

n= int(input())

cnt = 0
for i in range(1, n+1):
    if i*i > n:
        break

    if n % i == 0:
        cnt += 1

if n == 1:
    print("NO")

if n == 1:
    print("NO")
elif cnt == 1:
    print("YES")
else:
    print("NO")

2. 약수 구하기

# 2. 약수 구하기 => 제곱수를 조심한다.
#약수의 개수가 홀수 개이다 <==> 제곱수이다.
n = int(input())
prime = []

for i in range(1, n+1):
    if i*i > n:
        break

    if n % i == 0:
        prime.append(i)
        if i * i != n: #제곱수는 서로의 값이 같아서 똑같은 값이 들어가지 않게 해준다!
            prime.append(n // i)

# for i in range(len(prime))[::-1]:
#     prime.append(n//prime[i]) 이 방법도 가능.

print(*prime)

3. 소인수 분해

# 소인수 분해 => 계산하는 변수랑 i * i를 따로 
# n => a, b, c, d, e, f, g, h, i 다 연산 후 남는 i가 1이면 다 나누어진 것이고, 아니면 소수이다.
#a * b * c * d * e * f * g * h * i => n
n = int(input())

x = n
for i in range(2, n+1):
    if i * i > n:
        break

    while x % i == 0:
        print(i)
        x //= i

if n != 1: #1이라면 모두 나누어 떨어진다는 것
    print(n)

4. 유클리드 호제법

#유클리드 호제법
#최대공약수, 최소공배수
#a, b 두 수의 차의 약수가 공약수가 될 수 있다.
#8 44 의 공약수
#8 36 => 8 28 =>....
a, b = map(int, input().split())

A, B = a, b
while a % b != 0: # a가 큰수 b는 작은 수
    a, b = b, a % b #어차피 뺄셈을 반복하는 과정이므로 모듈러와 같음.

print(b) #최대 공약수
print(A * B // b) #최소 공배수 A와 B의 모든 수들이 더해진 것에서 겹치는 공약수인 최대공약수를 빼면 최소 공배수가 된다.

5. 에라토스테네스의 체

#5. 에라토스테네스의 체
#목표 : 1~n까지의 자연수 중 소수를 모두 출력한다.
#소수의 배수는 소수가 아니다!

n = int(input())

isPrime = [True for i in range(n+1)]

isPrime[1] = False
for i in range(2, n+1):
    if not isPrime[i]:
        continue
    
    for j in range(2 * i, n+1, i): #7 * (1~6)까지는 이미 처리가 되어있으니 7 * 7 부터 보겠다.
        isPrime[j] = False

print(*[i for i in range(n+1) if isPrime[i]]) #True인 것들 출력

#응용 : 2~n까지의 자연수 각각의 작은 소인수 출력

n = int(input())
prime = [-1 for i in range(n+1)]

for i in range(2, n+1):
    if prime[i] != -1:
        continue

    for j in range(i, n+1, i):
        if prime[j] == -1:
            prime[j] = i #같은 원리이지만 안찍혀있으면 가장 작은 소인수를 찍고 지나감.

print(*prime[2:])

6. 빠른 거듭 제곱

#6. 빠른 거듭제곱

#n ** m % 100000007 (n <= 100, m <= 1,000,000,000,000) 빠르게 구하기!

def pows(n, m):
    if m == 0:
        return 1
    
    ret = pows(n, m // 2)
    ret *= ret
    ret %= 1000000007

    if m % 2 == 0:
        return ret * ret
    else:
        return (ret * n) % 1000000007

보나스

# 1. 1~n까지 k의 배수의 개수
# = n // k 이다.

# 2. 팩토리얼에 곱해진 소수의 개수
#n!을 p로 몇번 나눌 수 있는지
#20!에 곱해진 2의 개수

# 1 ~ 20
# 20 // 2 + 20 // 4 + 20 // 8 + 20 // 16

# n!에 곱해진 p의 개수
# n //p + n // p^2 + n//p^3 + n // p^4 ....
n, p = map(int, input().split())

cnt = 0
x = p
while x <= n:
    cnt += n // x
    x *= p

print(cnt)