소인수분해 프로그램 예제

루비의 반복문과 조건문을 응용하여 만든, 합성수를 소인수분해하는 프로그램 예제입니다.

예제에 앞서 소수와 합성수의 개념을 먼저 설명드리고자 합니다.
여기서 소수는 0.1, 0.5 이런 소수(小數)가 아니라 합성수와 반대되는 개념입니다.
(한자로는 素數라 쓰는데 예전에는 小數와 구분하기 위해 '솟수'라고 표기하기도 했습니다. 여기서 말하는 소수를 '소쑤/솓쑤'라고 읽는 이유도 여기 있습니다.)
어떤 자연수 n을 다른 자연수 a로 나누었을 때 나머지가 0라고 한다면, a는 n의 약수가 됩니다.
즉, 6의 약수는 1, 2, 3, 6이 됩니다.
여기서 약수 중 자기 자신을 제외한 약수를 진약수라고 부릅니다. 앞에서 예로 든 6의 진약수는 6을 제외한 1, 2, 3입니다.

이제 소수와 합성수를 설명합니다.
소수는 2, 3, 5, 7과 같이 진약수가 1뿐인 수를 말하고, 합성수는 4, 6, 8, 9와 같이 1 외의 다른 진약수가 있는 수를 말합니다.
1은 소수에도 합성수에도 속하지 않습니다.
소인수분해라 함은 합성수를 소수의 곱셈식으로 바꾸는 것을 말합니다.
예를 들어 합성수 30을 소인수분해하면 2×3×5 이렇게 됩니다.

다음은 소인수분해를 루비로 구현한 예제 코드입니다.
본래 36같은 경우 2²×3² 이런 식으로 제곱을 쓰는 게 정석이지만 여기서는 2×2×3×3 이런 식으로 나오게끔 구현되어 있습니다.
(거듭제곱이 구현되는 버전도 이 포스트에 또 있습니다.)
프로그램 특성상 너무 큰 수를 입력할 경우 오랜 시간이 걸릴 수 있습니다.

# 소인수분해 예제

def prompt(*args)
    print(*args)
    gets
end

puts "소인수분해를 할 숫자를 입력하세요."
puts "(2 이상의 정수로 입력, 음수는 양수로 자동변환됩니다.)"
pp = prompt "> "

p_strt = (pp.to_i).abs    # 분해를 시작할 수
p_cur = p_strt            # 분해 과정의 수
p_div = 2                 # 분해를 위해 나눌 수
p_ptxt = ""               # 분해식을 쓰기 위한 문자열

puts sprintf("입력하신 수는 %d입니다.", p_strt)

if p_strt >= 2
  # 2 이상일 경우에만 소인수분해
  while p_cur > p_div
    # 나눌 수가 분해되는 수보다 크거나 같아질 때까지 반복
    if p_cur % p_div == 0
      # 나누어 떨어지면 분해
      p_cur /= p_div
      p_ptxt += (p_div.to_s + "*")
    else
      # 더 이상 분해되지 않으면 넘김
      p_div += 1
    end
  end
  p_ptxt += p_cur.to_s   # 마지막 남은 소수를 뒤에 출력
  puts sprintf("결과: %s", p_ptxt)
else
  # 0 또는 1을 입력할 경우
  puts "소인수분해를 할 수 없습니다."
end

아래는 이 코드를 실행한 스크린샷입니다.

또 다른 버전으로 거듭제곱을 구현한 버전도 있습니다.
다만, 첨자를 구현하기 어려운 CUI의 특성상 앞에서 예를 든 2²×3² 같은 경우는 (2**2)*(3**2) 이런 식으로 표현됩니다.
(루비에서 ** 연산자는 거듭제곱 연산자입니다. 예: 2**4 = 16)

# 소인수분해 예제 (거듭제곱 구현)

def prompt(*args)
    print(*args)
    gets
end

def powtext(i, j)
  if j > 1
    return sprintf("(%d**%d)", i, j)
  else
    return sprintf("(%d)", i)
  end
end

puts "소인수분해를 할 숫자를 입력하세요."
puts "(2 이상의 정수로 입력, 음수는 양수로 자동변환됩니다.)"
pp = prompt "> "

p_strt = (pp.to_i).abs    # 분해를 시작할 수
p_cur = p_strt            # 분해 과정의 수
p_div = 2                 # 분해를 위해 나눌 수
p_pow = 0                 # 거듭제곱 수
p_ptxt = ""               # 분해식을 쓰기 위한 문자열

puts sprintf("입력하신 수는 %d입니다.", p_strt)

if p_strt >= 2
  # 2 이상일 경우에만 소인수분해
  while p_cur > p_div
    # 나눌 수가 분해되는 수보다 크거나 같아질 때까지 반복
    if p_cur % p_div == 0
      # 나누어 떨어지면 분해
      p_cur /= p_div
      p_pow += 1
    else
      # 더 이상 분해되지 않으면 넘김
      p_ptxt += powtext(p_div, p_pow) + "*" if p_pow > 0
      p_pow = 0
      p_div += 1
    end
  end
  p_pow += 1
  p_ptxt += powtext(p_cur, p_pow)   # 마지막 남은 소수를 뒤에 출력
  puts sprintf("결과: %s", p_ptxt)
else
  # 0 또는 1을 입력할 경우
  puts "소인수분해를 할 수 없습니다."
end

아래는 이 코드를 실행한 스크린샷입니다.

유용하게 활용하시기 바랍니다.