★Number Theory Upper-Beginner I - 15 Solved★

★ 2609 최대공약수와 최소공배수 ★

 

A, B = map(int,input().split())

a, b = A, B
GCD, LCM = 0, 0

while True:
    if A == B:
        GCD = A
        print(GCD)
        break
    else:
        if A >= B:
            A = abs(A-B)
        else:
            B = abs(A-B)
    
print(a*b//GCD)

 

🧚‍♂️ 최대공약수, 최소공배수 전형적인 알고리즘!

 

① math module - gcd, lcm

import math

a, b = map(int, input().split())

print(math.gcd(a, b))
print(math.lcm(a, b))

 

② 유클리드 호제법 사용

→ 해결법은 function 사용 - 함수를 사용하면, 해당 함수의 출력값만 리턴해주고, 매개변수로 넣은 A와 B는 변하지 않는다. GCD와 LCM 각각 함수를 사용해 코딩하면 됨

a, b = map(int, input().split())

def gcd(a, b):
    while b > 0:
        a, b = b, a % b
    return a

def lcm(a, b):
    return a * b // gcd(a, b)

print(gcd(a, b))
print(lcm(a, b))

 

★ 유클리드 호제법) a를 b로 나눈 나머지를 r이라 하면, a와 b의 최대공약수는 b와 r의 최대공약수 ★

(1) function gcd) 

→ 한 쪽 수 b가 0이 될 때까지 계속해서 나누고 나온 나머지를 a에 계속 저장해, a와 0이 되는 b가 나올 때, a가 최대공약수가 된다.

a, b = b, a%b

 

(2) function lcm)

→ gcd를 구했다면, 두 수를 곱해 최대공약수로 나눈 결과가 최소공배수 (A x B = G x L)

 

③ 공약수 중 최댓값

a, b = map(int, input().split())

tmp = []
for i in range(1, min(a,b) + 1):
    if a % i == 0 and b % i == 0:
        tmp.append(i)

print(max(tmp))
print(max(tmp) * (a // max(tmp)) * (b // max(tmp)))

 

 

→ 또는, 최솟값 1부터 시작하는게 아니라, 어차피 '최댓값'을 구하는 것이므로, 두 수 중 한 수 b부터 거꾸로 시작해 공약수를 찾아내, 찾으면 바로 최대공약수가 되어 선정

import sys
input = sys.stdin.readline
 
a, b = map(int, input().split())
 
for i in range(b, 0, -1):
    if a % i == 0 and b % i == 0:
        print(i)
        print(i * a // i * b // i)
        exit()

 

④ 유클리드 호제법 - 재귀함수 사용

→ a와 b에 b와 a%b를 넣는 것으로, gcd 함수를 만들고 return문에 gcd(b, a%b)를 넣어 b가 0이 될 때까지 계속 함수를 재귀적으로 반복하게!

a, b = map(int, input().split())

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)
    
print(gcd(a, b), a*b//gcd(a, b))

---

★ 1037 약수 ★

 

N = int(input())

divisors = list(map(int, input().split()))
n = sorted(divisors)
print(n[0] * n[len(n)-1])

---

★ 1934 최소공배수 ★

import sys
input = sys.stdin.readline

for _ in range(int(input())):
    A, B = map(int, input().split())
    
    a,b=A,B
    while b!= 0:
        a,b=b,a%b
    
    print(A*B//a)

 

🧚‍♂️ 최대공약수 & 최소공배수 & 두 수의 관계

→ 두 수 A와 B가 있고, 두 수의 최대공약수를 G, 최소공배수를 L이라 한 뒤, A를 G로 나눈 몫을 a, B를 G로 나눈 몫을 b라 하면

★ L = G * a * b ★

★ L * G = A * B ★

 

🧚‍♂️ math 사용이 아닌 경우, 위와 같이 유클리드 호제법으로 G를 구한 뒤, 위 L과 G의 공식에 의해 L을 구하면 시간초과 없이 빠른 시간 내에 코드가 돌아가는 걸 확인 가능

---

★ 15633 Fan Death ★

n = int(input())
res = 0
for i in range(1,int(n**(1/2))+1,1):
    if n%i == 0:
        res += i
        if i != n**(1/2):
            res += (n//i)
print(res*5-24)

 

🧚‍♂️ 주어진 수의 약수의 합을 구하는 문제

→ 1부터 주어진 수 끝까지 돈다면 시간 효율성에서 비효율적이라 판단하여 주어진 수의 제곱근 범위까지만 돌게 하였다.

 

① range()에 의해 n**(1/2)를 int()한다음, 1을 더해 정확히 for문이 int(n**(1/2))까지만 돌 수 있게 한다.

② 만약 제곱수일 경우 두 번 카운트되는 것을 방지하기 위해 i != n**(1/2) 조건을 건다.

(※이 때, i != int(n**(1/2))일 경우 제곱수가 아님에도 조건이 True되는 경우가 있으므로 (ex) 3의 약수 1) int는 반드시 제외!)

---

★ 6030 Scavenger Hunt ★

P,Q=map(int,input().split())
Ps = [i for i in range(1,P+1) if P%i == 0]
Qs = [i for i in range(1,Q+1) if Q%i == 0]
for p in Ps:
    for q in Qs:
        print(p,q)

---

★ 9506 약수들의 합 ★

 

while 1:
    n=int(input())
    if n==-1:break
    end=int(n**(1/2))
    l=[]
    for i in range(2,end+1):
        if n%i==0:
            l.extend((i,n//i))
    l.append(1)
    if sum(l)==n:
        l.sort()
        print(n,'=',end=' ')
        print(*l,sep=' + ')
    else:print(f'{n} is NOT perfect.')

 

🧚‍♂️ 전체를 돌지 않고 수의 root범위까지만 돌아 약수인지 판단

---

★ 6888 Terms of Office ★

X=int(input())
Y=int(input())

for i in range(X,Y+1,60):
    print(f'All positions change in year {i}')

 

🧚‍♂️매 4년, 2년, 3년, 그리고 5년의 주기를 갖는 선출 사이클에서 어떤 해가 동시에 뽑는 지 알아보는 문제. 4, 2, 3, 5의 최소공배수인 60년의 주기를 가질 때 해당된다.

---

★ 14682 Shifty Sum ★

 

print(int(input())*int('1'*(int(input())+1)))

 

🧚‍♂️ 단순 반복문으로도 풀 수 있지만, shitfy sum의 성질을 이용해 정수론 관점으로 해결해보면, 동일한 수가 왼쪽으로 한 칸씩 움직이므로 한 칸씩 움직일 때마다 동일한 수의 10배만큼 해당 수가 커진다. 따라서 x번 이동했다면 1이 x번 있고 맨 마지막 수가 0인 배수만큼 곱해짐

 

🧚‍♂️추가로, 나 자신도 더해져야 하므로 여기서 1을 더함 → 결과적으로 1이 (x+1)개로 구성된 수만큼 곱해짐

---

★ 8678 Zbiór ★

 

import sys
input=sys.stdin.readline

for _ in range(int(input())):
    a,b=map(int,input().split())
    if b%a==0:print('TAK')
    else: print('NIE')

 

🧚‍♂️ a의 모든 약수는 b의 모든 약수에 포함된다는 건, a가 b에 나눠진다는 뜻. b를 a로 나눈 나머지가 0이다.

---

★ 27465 소수가 아닌 수 ★

 

print(10**9)

 

🧚‍♂️ 10의 9승은 무조건 소수가 아니므로 항상 답이 됨!

---

★ 5086 배수와 약수 ★

 

while 1:
    a,b=map(int,input().split())
    if (a,b) == (0,0): break
    if b%a == 0: print('factor')
    elif a%b == 0: print('multiple')
    else: print('neither')

---

★ 11653 소인수분해 ★

 

N=int(input())

def isPrime(n):
    end=int(n**(1/2))
    for i in range(2,end+1):
        if n%i==0:
            return False
    return True
if N==1:
    pass
else:
    ans=[]
    x=2
    while N>1:
        if len(ans) != 0 and N%ans[-1] == 0:
            late_prime = ans[-1]
            ans.append(late_prime)
            N//=(late_prime)
        else:
            if N%x == 0:
                if isPrime(x):
                    ans.append(x)
                    N//=x
            x+=1
    print(*ans,sep='\n')

 

🧚‍♂️ 소인수분해는 소수의 곱으로 표현되게끔 주어진 수를 소수로만 표현하는 분해이다.

 

🧚‍♂️ 위와 같이 나누어지는 지, 소수인지 확인한 다음 1씩 더해가며 일일이 확인하는 과정도 있다.

 

🧚‍♂️+ 시간 단축 풀이 + (소인수분해 풀이 반드시 기억!) 🧚‍♂️

1) 2부터 sqrt{N}까지 확인 (2부터 차례대로 확인하면 소수인지 확인할 필요 x)

2) 만약 나누어진다면, 동일한 수로 계속 나눌 수 있는 지 while문으로 확인

3) root까지 확인하였으므로 최종 결과가 만약 1이 아니라면 큰 소수가 하나 남은 것이므로 마지막 가장 큰 소인수 출력하고 끝

(더 큰 수의 소인수분해는 euler sieve 활용: 별도 포스팅 참조)

n = int(input())
for i in range(2, int(n**0.5)+1):
    while n%i == 0:
        n //= i
        print(i)
if n!=1:print(n)

---

★ 1145 적어도 대부분의 배수 ★

 

🧚‍♂️세 수의 최소공배수는 (1)과 (2)의 최소공배수를 구한 결과와 (3)과의 최소공배수

 

🧚‍♂️ 즉, N개의 최소공배수는 (1)과 (2)의 최소공배수 구한 결과와 (3)과의 최소공배수 - 그 다음 구한 결과와 (4)와의 최소공배수 .. 이렇게 계속 update

import math
from itertools import combinations
def lcm(a,b):
    return (a*b)//(math.gcd(a,b))

l=list(map(int,input().split()))
ans=1000000
for numbers in combinations(l,3):
    a,b,c=numbers
    x = lcm(lcm(a,b),c)
    ans=min(ans,x)
print(ans)

 

* 1000000로 ans 초기값 설정 - combinations()로 세 쌍씩 choice - ans update

* 두 수의 최소공배수 = (두 수의 곱) / (두 수의 최대공약수)

---

★ 1978 소수 찾기 ★

 

① 2부터 (자기자신 -1) 까지의 모든 수를 자기자신에서 나누었을 때 나머지가 모두 0이 아니다. O(N)

→ 나머지가 모두 0이 아닌 수의 개수가 (자기자신 -2)라면 소수

result = 0
N = int(input())

for number in list(map(int, input().split())):

    cnt = 0       
    for j in range(2,number):
        if number%j != 0:
            cnt += 1
        
    if cnt == (number -2):
            result += 1 
            
print(result)

 

② 약수의 개수가 2이다 O(N)

r=0
input()
for n in list(map(int,input().split())):
    l = [j for j in range(1,n+1) if n%j==0]
    if len(l) == 2 : r+=1
print(r)

 

③ N의 제곱근까지만 검사 O(\sqrt{N})

→ 약수는 N의 제곱근까지만 나누어지는 지 검사하면 됨. (약수는 N의 제곱근 범위 내에서 반드시 존재하므로 범위 탐색 시간 효율적으로 줄일 수 있음)

→ 다만 N의 약수의 개수가 2가 아닌 1로 판별해야 하고, 1은 소수가 아니므로 1만 카운트에서 제외하는 점을 주의!

r=0
input()
for n in list(map(int,input().split())):
    if n == 1:
        continue
    l=[j for j in range(1,int(n**(1/2))+1)if n%j==0]
    if len(l)==1:r+=1
print(r)

 

→ 제곱근까지만 검사해서 72ms → 68ms로 시간 소요 덜함!

 

④ N/2까지만 검사 O(N)

→ ③에 비해 시간복잡도는 더 소요되지만, 일일이 N까지 검사하는 풀이에 비해선 훨씬 효율적!

→ N의 약수는 최대 N/2 범위 이내에만 들어가 있음을 안다는 조건 하에 진행하는 풀이이다.

 

⑤ 에라토스테네스의 체

🌟 소수 판별하면 무조건 알아야 하는 판별법! 추후 문제로 설명 예정

 

⑥ 소수는 2 그리고 3 그리고 6으로 나눈 나머지가 1또는 5이다.

→ 모든 자연수는 6k, 6k+1, 6k+2, 6k+3, 6k+4, 6k+5로 나타낼 수 있고, 여기서 6k+1과 6k+5 제외 다른 형태는 2또는 3으로 나누어지는 것을 확인할 수 있으므로 소수가 존재한다면 6으로 나눈 나머지가 1또는 5일 것이다. 여기서 2와 3만 배제한다. 

r=0
input()
for n in list(map(int,input().split())):
    if n == 1: continue
    if n%6 in [1,5] or n in [2,3]:
        l=[j for j in range(1,int(n**(1/2))+1)if n%j==0]
        if len(l)==1:r+=1
print(r)

---

★ 2581 소수 ★

 

import math
def is_prime(n):
    if n == 1:
        return False
    for j in range(2,int(math.sqrt(n))+1):
        if n%j==0:
            return False
    return True

M=int(input())
N=int(input())
flag,ans,least=0,0,0

for i in range(M,N+1):
    if is_prime(i):
        ans+=i
        if flag==0:
            least=i
            flag+=1

if least==0:print(-1)
else:print(ans,least,sep='\n')

---