[Python]BAEKJOON 4335번 서로소

https://www.acmicpc.net/problem/4355 

4355번: 서로소

 

11689번 문제와 다를 게 없다. 아래 링크 참고.

1) 0을 입력 받기 전까지 while문에서 계속 순환하고, 

2) 1이 입력되면 0이 출력되어야 한다는 점만 다르다. (입력으로 주어진 n마다 n보다 작으면서 서로소인 양의 정수의 수를 출력한다.)라는 조건 때문. 

https://seolpark.tistory.com/76 

[Python]BAEKJOON 11689 번 GCD(n, k) = 1

 

 

Sol1

while True:
    N = int(input())
    if N == 0: break
    lst = []
    res = N
    for i in range(2,int(N**0.5)+1):
        if N%i == 0:
            lst.append(i)    #소인수 구함
            lst.append(N//i)
    lst = list(set(lst))
    if lst: 
        for i in lst:
            for j in range(2,int(i**0.5)+1):   #소수 구함 
                if i%j == 0:break  #합성수 
            else: res *= (1-1/i)
        print(int(res))
    else:
        if N ==1: print(0)
        else: print(N-1)

 

 

 

 

Sol2 

while True: 
    N = int(input())
    if N==0: break
    if N==1: 
        print(0)
        continue
    res = N 
    for i in range(2,int(N**0.5)+1):
        if N%i == 0:
            while N%i ==0:
                N //= i
            res *= (1-1/i)
    if N>1:
        res *= 1-1/N 
    print(int(res))