Problem 3 : 가장 큰 소인수 구하기

프로그래밍 공부를 위해 Projetct Euler의 문제 풀이를 연습하는 내용입니다.
문제(problem), 제 답변(answer), 추천하는 타인 답변(solution)으로 구성되어 있습니다.
기본적으로 풀이는 R을 사용하였지만, 일부 연습을 위해 Python으로도 구현해 보았습니다.

Problem

• 번호 : 3
• 제목 :
  가장 큰 소인수 구하기
• 설명 :
  어떤 수를 소수의 곱으로만 나타내는 것을 소인수분해라 하고, 이 소수들을 그 수의 소인수라고 합니다.
  예를 들면 13195의 소인수는 5, 7, 13, 29 입니다.
  600851475143의 소인수 중에서 가장 큰 수를 구하세요.

Answer & Solution - R

• 어떤 수(num)를 인자로 받아 소인수 집합(num_list)을 구하는 함수 작성
• 2부터 어떤 수(num)까지 1씩 증가시키면서 나머지(num %% i == 0)가 0인 값들을 소인수 집합(num_list)에 추가
• code : R 코드

# Answer-1

problem3 <- function(num) {

  num_list = vector()

  for (i in 2:num) {

    while (num %% i == 0){
      num_list = c(num_list, i)
      num = num / i
      cat(i, "\t| ", num_list, "\n")
    }
    if (num == 1){
      break
    }
  }
  return(num_list)
}

problem3(13195)
# [1]  5  7 13 29 

problem3(600851475143)
# Error in problem3(600851475143) : 
# long vectors not supported yet: eval.c:6387 

# Answer-2

# for문은 range를 모두 vector화하여 계산하기 때문에 메모리를 많이 사용
# while문으로 처리하면 가능하다.
# 확인 1 : for문과 while의 처리 방식의 차이
# check point 1 : difference between for and while 
# 확인 2 : while 문 사용시 =< 안되고 <= 된다
# check point 2 : 조건식 사용
# https://support.bioconductor.org/p/118016/

problem3 <- function(num) {

  num_list = vector()
  i = 2

  while (i <= num){

    while (num %% i == 0){
      num_list = c(num_list, i)
      num = num / i
      cat(num, "\t| ", num_list, "\n")
    }
    if (num == 1){
      break
    }
    i = i + 1
  }
  return(num_list)
}

problem3(13195)
# [1]  5  7 13 29
problem3(600851475143)
# [1]   71  839 1471 6857

# Solution

prime <- function(num){
  factor=2
  while (num != 1){
    if (num %% factor == 0){
      cat(num, "\t| ", factor, "\n")
      num = num / factor
    } else { 
      factor = factor + 1
    }
  }
  return(factor)
}

prime(600851475143)
# 6857

Answer & Solution - Python

• code : Python

# Answer

import time

def logging_time(original_fn):
    def wrapper_fn(*args, **kwargs):
        start_time = time.time()
        result = original_fn(*args, **kwargs)
        end_time = time.time()
        print("WorkingTime[{}]: {} sec".format(original_fn.__name__, end_time-start_time))
        return result
    return wrapper_fn

@logging_time
def problem3(num):
    num_list = []

    for i in range(2, num):

        while num % i == 0:
            num_list.append(i)
            num = num / i
            print(num, " | ", num_list)

        if num == 1:
            break

    return num_list

# Solution
@logging_time
def prime(num):
    factor=2
    while num != 1:
        if num%factor == 0:
            print(num, factor)
            num = num / factor
        else:
            factor +=1
    return factor

if __name__ == '__main__':

    print(problem3(13195))
    # [5, 7, 13, 29]

    print(problem3(600851475143))
    # [71, 839, 1471, 6857]

    print(prime(600851475143))
    # 6857

System Info.

PyCharm 2019.1 EAP (Community Edition)
Build #PC-191.6014.12, built on March 6, 2019
JRE: 11.0.2+159 amd64
JVM: OpenJDK 64-Bit Server VM by JetBrains s.r.o
Windows 7 6.1
R version 3.5.2 (2018-12-20)
Python 3.6.6
Platform: x86_64-w64-mingw32/x64 (64-bit)
Running under: Windows 7 x64 (build 7601) Service Pack 1
RStudio version 1.1.463