작성일 In 댓글:

Project Euler

  • 공식 홈페이지 - projecteuler.net
  • 한글 번역 - projecteuler @kr
  • (HackerRank) ProjectEuler+ - hackerrank.com

Problem

Largest prime factor


참고 - stackoverflow.com

problem <번역>

solution

Simple Code

소수(prime number)룰 구하는 방법으로 흔히 2가지 알고리즘을 사용한다
밀러-라빈 소수 판별법 (Miller-Rabin Primality Test) 과
에라토스테네스의 체 (Sieve of Eratosthenes) 이다.
문제는 소인수(prime factor) 즉, 소수이면서 약수인 수 중 가장 큰 값을 찾는 것이다.
아래는 밀러-라빈 소수 판별법 알고리즘을 사용한 풀이이다.

003_Largest_prime_factor.py
def largest_prime_factor(N):
  num = 2
  prime = []

  while N != 1:
      if N % num:
          num += 1
      else:
          N = N // num
          prime.append(num)

  return prime[-1]


print(largest_prime_factor(600851475143))
HackerRank

에라토스테네스의 체 알고리즘을 사용한 풀이는 다음과 같다

003_for_HacerRank.py
from math import sqrt


def largest_prime_factor(N):
  prime = []

  while N % 2 == 0:
      prime.append(2)
      N //= 2
  for i in range(3, int(sqrt(N))+1, 2):
      while N % i == 0:
          prime.append(i)
          N //= i

  if N > 2:
      prime.append(N)

  return max(prime)


if __name__ == '__main__':
  for _ in range(int(input())):
      N = int(input())
      print(largest_prime_factor(N))

파이썬에는 사용자의 편의를 위해 sympy 모듈 에서 primefactors를 제공한다.
(소수를 구하고 싶다면 primerange(1, N)을 사용하면 된다. 아래는 100까지의 소수와 소인수를 구한 예제)

003_sympy_primefactor.py
from sympy import primerange
from sympy import primefactors

print(*primerange(1, 100))  # 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
print(primefactors(100))    # [2, 5]

에라토스테네스의 체 보다 밀러-라빈 소수 판별법이 간단하고 수행 속도도 더 빠르다
sympy 모듈의 함수들도 잘 기억하고 있자!

작성일 In 댓글:

Project Euler

  • 공식 홈페이지 - projecteuler.net
  • 한글 번역 - projecteuler @kr
  • (HackerRank) ProjectEuler+ - hackerrank.com

Problem

Even Fibonacci numbers


problem <번역>

solution

Simple Code

문제에 충실하게 4백만(4,000,000) 보다 작은 피보나치 수열에서 짝수들의 합을 구했다
(짧게 코드를 구현할 수 있지만 가독성을 위해 피보나치 수열을 만들고 짝수들의 합을 구하는 함수를 따로 정의했다)

002_Even_Fibonacci_numbers.py
def fibonacci(max_num):
    numbers = [1, 2]

    while numbers[-1] < max_num:
        numbers.append(numbers[-2] + numbers[-1])

    return numbers[:-1]


def sum_of_the_even_valued(numbers):
    total = 0
    for n in numbers:
        if n % 2 == 0:
            total += n

    return total

print(sum_of_the_even_valued(fibonacci(4000000)))
HackerRank

위 풀이 방식을 그대로 적용해도 문제 없이 모든 테스트 케이스를 통과한다.

002_for_HacerRank.py
def fibonacci(max_num):
    numbers = [1, 2]

    while numbers[-1] < max_num:
        numbers.append(numbers[-2] + numbers[-1])

    return numbers[:-1]


def sum_of_the_even_valued(numbers):
    total = 0
    for n in numbers:
        if n % 2 == 0:
            total += n

    return total


if __name__ == '__main__':
    T = int(input())
    for _ in range(T):
        N = int(input())
        print(fibonacci(N))
        print(sum_of_the_even_valued(fibonacci(N)))

하지만 짝수인 피보나치 수열들을 잘 살펴보면 [2, 8, 34, 144, 610, …]
8 = 2 * 4 + 0
34 = 8 * 4 + 2
144 = 34 * 4 + 8
610 = 144 * 4 + 34
즉,
다음 짝수 = 이전 짝수 * 4 + 전전 짝수
라는 규칙을 발견할 수 있다

002_even_fibonnacci.py
def even_fibonacci(max_num):
    prev, cur, total = 0, 2, 0

    while cur <= max_num:
        total += cur

        prev, cur = cur, cur * 4 + prev

    return total


if __name__ == '__main__':
    T = int(input())
    for _ in range(T):
        N = int(input())
        print(even_fibonacci(N))

피보나치 수열에서 짝수들은 3칸씩 떨어져 있음을 알게되었다.
불필요하게 모든 피보나치 수열을 구하지 말자

작성일 In 댓글:

Project Euler

  • 공식 홈페이지 - projecteuler.net
  • 한글 번역 - projecteuler @kr
  • (HackerRank) ProjectEuler+ - hackerrank.com

Problem

Multiples of 3 and 5


problem <번역>

solution

Simple Code

반복문을 통해 3과 5로 나누어 떨어지는 것들만 조건문을 통해 합하면 된다

001_multiples_of_3_and_5.py
def multiples_3_5(N):
    return sum([num for num in range(N) if (num % 3 == 0 or num % 5 == 0)])

print(multiples_3_5(1000))
HackerRank

HackerRank에 등록된 테스트 케이스들은 해당 문제의 풀이를 조금 더 까다롭게 검사한다.
이번 문제에서 위 풀이를 사용하면 TestCase 2, 3에서 ‘Terminated due to timeout’ 에러를 발생 시킨다.(아래 코드는 테스트 케이스를 입력 받는 부분만 추가한 것)
즉, 최적화된 방법으로 문제를 풀어야 한다.

Terminated due to timeout
def multiples_3_5(N):
    return sum([num for num in range(N) if (num % 3 == 0 or num % 5 == 0)])

if __name__ == '__main__':
    T = int(input())
    for _ in range(T):
        N = int(input())
        print(multiples_3_5(N))

arithmetic sequence - mathsisfun.com
반복문을 제거해서 시간 복잡도를 O(1)로 바꿔준다. (등차수열을 활용해 결과를 한번에 구한다)
주의할 것은 등차수열의 개수를 구할 때 // 연산자를 사용하는 것이 좋다.(int((N-1)/3) 이렇게 구하면 안된다)

001_for_HacerRank.py
def arithmetic_sequence(mul):
    return mul * (mul + 1)

T = int(input())
for _ in range(T):
    N = int(input())

    mul_3 = (N-1) // 3
    mul_5 = (N-1) // 5
    mul_15 = (N-1) // 15 # lcm of 3, 5 = 15
    print((3 * arithmetic_sequence(mul_3) + 5 * arithmetic_sequence(mul_5) - 15 * arithmetic_sequence(mul_15)) // 2)

가독성(readability)을 생각했을 때, 반복문을 사용한 방법이 더 좋은 것 같지만 본 프로젝트의 의도가 수학적인 해결 방법을 고민해 보는 것이기 때문에 아래의 풀이 방법을 정확히 이해하는 것이 중요하다