파이썬 소인수 분해

조회수 49회
import math
N = int(input())
p=[]

if N == 1 :
    print("error")

while N !=1:
    if len(p)==0:
        start=2
    else:
        start=p[-1]
    for i in range(start,N+1):
        if N % i==0:
            #print(i)
            p.append(i)
            N=N//i
            break
        else:
            continue

소인수 분해는 할 줄 알겠는데

[입력예시]
135

[출력예시]
3 ^ 3 X 5 ^ 1

이런식으로 출력할 줄 모르겠습니다.

도와주십시오

  • 코드를 알아보기 힘들어서 대략 아이디어만 말씀드리자면, 딕셔너리를 쓰셔서 키 값과 밸류 값으로 출력하면 좋지 않을까 하네요. dh jung 2021.5.4 15:30

1 답변

  • p 를 약수들의 리스트에서, (소수, 몇개) 의 리스트로 바꾸어 수집하도록 수정합니다.

    그걸 문제가 원하는 출력형식에 맞도록 join 문 등을 이용하여 출력합니다.

    1. 이렇게 고치고 보면, 가장 바깥쪽의 while N != 1 (를 비롯한 몇 라인)은 아마도 필요 없을 것 같네요.
    2. 매우큰 소수를 입력을 주었을 때, 좀 비효율적입니다. 더 빨리 루프를 빠져나갈 수 있습니다.
    
    import math
    N = int(input())
    p=[]
    
    if N == 1 :
        print("error")
    
    while N !=1:
        if len(p)==0:
            start=2
        else:
            start=p[-1]
        for i in range(start,N+1):
            count = 0
            while N % i==0:
                #print(i)
                count += 1
                N=N//i
            if count:
                p.append((i, count))
    
    
    print('x'.join(' %d^%d '%(e[0], e[1]) for e in p))          
    

답변을 하려면 로그인이 필요합니다.

Hashcode는 개발자들을 위한 무료 QnA 사이트입니다. 계정을 생성하셔야만 답변을 작성하실 수 있습니다.

(ಠ_ಠ)
(ಠ‿ಠ)

ᕕ( ᐛ )ᕗ
로그인이 필요합니다

Hashcode는 개발자들을 위한 무료 QnA사이트 입니다. 계정을 생성하셔야만 글을 작성하실 수 있습니다.