[python] 백준 13412 - 서로소 쌍

두 자연수 A, B의 최대공약수를 GCD(A, B)라고 할 때, A와 B가 서로소면 GCD(A, B) = 1

두 자연수 A, B의 최소공배수를 LCM(A, B)라고 할 때, A와 B가 서로소면 LCM(A, B) = A x B

자연수 N이 주어질 때, N을 최소공배수로 하는 서로 자연수 쌍의 개수 출력

 

 

def gcd(a,b):  #최대공약수
    if b==0:
        return a
    else:
        return gcd(b,a%b)  

def lcm(a,b):  #최소공배수
    return (a*b)//gcd(a,b)

def divisor(n):  #약수 구하기(참조)
    n=int(n)
    divisor=[]
    divisor_back=[]
    for i in range(1,int(n**(1/2))+1):
        if n%i==0:
            divisor.append(i)
            if i!=n//i:
                divisor_back.append(n//i)
    return divisor+divisor_back[::-1]
    
case=int(input())  #테스트케이스의 개수

for i in range(case):
    cnt=0  #서로소 쌍의 개수
    n=int(input())
    li=divisor(n)  #n의 약수 저장
    if len(li)%2==0: #약수의 개수가 짝수면
        li_1=li[:len(li)//2] #반반 나누기
        li_2=li[len(li)//2:]
        li_2=li_2[::-1]  #뒤에꺼는 뒤집어주기
        li2=[[x,y] for x,y in zip(li_1,li_2)] #zip함수로 묶어주기
    else: #약수의 개수가 홀수면
        li_1=li[:len(li)//2]
        li_2=li[len(li)//2+1:]
        li_2=li_2[::-1]
        li2=[[x,y] for x,y in zip(li_1,li_2)]
        li2.append([li[len(li)//2],li[len(li)//2]])  #중간 숫자는 두개로 묶어주기
    
    for j in range(len(li2)):
        if lcm(li2[j][0],li2[j][1])==li2[j][0]*li2[j][1]: #lcm(a,b)==a*b이면
            cnt+=1  #cnt+=1
        else:
            pass
    #print(li2)
    print(cnt)

약수 구하는 방법은 아래를 참조했다.

그냥 for문으로 넣는것 말고 효율적인 코드를 찾다가 구글링으로 찾았다!

https://inuplace.tistory.com/459

[알고리즘 연습] 약수 구하기 효율화 (by Python)