백준 4355번 - 서로소

1. 문제 난이도

---

2. 문제설명

양의 정수 n이 주어졌을 때, n보다 작은 양의 정수 중에서 n과 서로소인 수 개수를 구하는 문제이다.

<INPUT>

각 줄에 입력값 n이 하나씩 주어진다.

입력의 끝은 0이다.

 

<OUTPUT>

각 input n에 대해 문제의 답을 출력한다.

---

3. 아이디어

먼저 수학적인 아이디어로 오일러 파이 함수를 사용했다.

오일러 파이 함수에 대해서는 아래의 블로그 글을 참고하면 좋을 것 같다.

https://mathinguys.tistory.com/4

 

내가 푼 방식의 아이디어는 

1. 입력값 n의 약수 구하기

2. 약수 중 합성수를 제외하기

3. 오일러 파이로 조건에 맞는 개수 구하기

이다.

 

또 원래 1의 오일러파이 값은 1이지만

이 문제에서는 n=1일 때 n보다 작은 양의 정수는 없으므로 0을 출력해야한다.

---

4. 구현

<is_prime(n)함수>

n이 소수라면 True

아니라면 False

 

<get_primediv(n)함수>

n의 소인수만 리스트로 반환

def is_prime(n):
    for i in range(2,int(n**(1/2))+1):
        if n%i==0:
            return False
    return True

def get_primediv(n):
    li=[]
    for i in range(1, int(n**(1/2))+2):
        if n%i==0:
            li.append(i)
            li.append(n//i)
    li=list(set(li))
    li2=[]
    for i in li:
        if is_prime(i)==False:
            li2.append(i)
    for i in li2:
        li.remove(i)
    li.remove(1)
    return li

while(1):
    n=int(input())
    if n==0:
        break
    elif n==1:
        print(0)
    else:
        ans=n
        for i in get_primediv(n):
            ans=ans*(i-1)//i
        print(ans)

댓글, 오류지적 모두 감사합니다