[백준] 11653번(소인수분해)

백준 11653번

최종 제출 코드

number = int(input())

def prime_check(number):
  for i in range(2, number+1):
    if number%i==0:
      return i

while number >= 2:
  modifier = prime_check(number)
  number = int(number/modifier)
  print(modifier)

• 나누어 떨어지는 값이 있는지 체크하는 함수 prime_check() 정의
• 소수일 경우, 자기 자신을 return
• prime_check()를 number가 1이 될 때까지, 즉 더 이상 소인수분해가 안 될 때까지 반복

다른 사람이 작성한 코드

N=int(input())
i=2

while N>=i*i:
  while N%i==0:
    print(i)
    N/=i
  i+=1
  
if N!=1:
  print(int(N))

• N이 i의 제곱수보다 작을 때, 즉 i가 N의 1/2승 이하일 경우에 대해서만 검사
  => 소인수분해가 가능한 경우, N을 나눌 수 있는 가장 큰 자연수는 N의 1/2승이다
  => 이 경우 소인수분해가 불가능한 경우에 대한 검사 불가능
• while N%i==0에 의해 i로 나누어 떨어지지 않을 때까지 반복
  => 재귀함수 사용할 필요 없음
• if N!=1로 소인수분해가 불가능한 경우(N이 1이 아닌 경우)를 검사하여 그 값을 출력

코드 출처