파이썬에서 정렬된 순서로 주어진 숫자의 모든 소인수를 찾는 프로그램

1보다 큰 숫자 n이 있다고 가정하면 모든 소인수를 찾아 정렬된 순서로 반환해야 합니다. 우리는 소수의 곱으로 숫자를 쓸 수 있습니다. 그들은 소인수입니다. 그리고 동일한 소인수가 두 번 이상 나타날 수 있습니다.

따라서 입력이 42와 같으면 출력은 [2, 3, 7]이 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• res:=새 목록
• n mod 2가 0과 같을 때 do
  • res 끝에 2 삽입
  • n :=n/2의 몫
• 3에서 (n의 제곱근) 범위에 있는 i에 대해 2단계에서 증가
  • n mod i가 0인 동안 do
    • res 끝에 i 삽입
    • n :=n/i의 몫
• n> 2이면
  • res 끝에 n 삽입
• 반환 결과

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

class Solution:
   def solve(self, n):
      res=[]
      while n%2==0:
         res.append(2)
         n//=2
      for i in range(3,int(n**.5)+1,2):
         while n%i==0:
            res.append(i)
            n//=i
      if n>2:
         res.append(n)
      return res
ob = Solution()
print(ob.solve(42))

입력

42

출력

[2, 3, 7]