11653. 소인수분해

업데이트 시간 : 2023-01-25 05:40:44 +0000

[Bronze I] 소인수분해 - 11653

문제 링크

성능 요약

메모리: 32540 KB, 시간: 640 ms

분류

수학(math), 정수론(number_theory), 소수 판정(primality_test)

문제 설명

정수 N이 주어졌을 때, 소인수분해하는 프로그램을 작성하시오.

입력

첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다.

출력

N의 소인수분해 결과를 한 줄에 하나씩 오름차순으로 출력한다. N이 1인 경우 아무것도 출력하지 않는다.

💡 Solutions

📄 소인수분해.py

import math
import sys

N = int(sys.stdin.readline())

def isPrime(num):
  for i in range(2, int(math.sqrt(num)+1)):
    if num % i == 0:
      return False
  return True
div = 2

if N != 1:
  if(isPrime(N)):
    print(N)

  while not isPrime(N):
    if (isPrime(div)):
      while N % div == 0:
        print(div)
        N //= div
    div += 1
    if(isPrime(N) and N != 1):
      print(N)