Commits

Tetsuya Morimoto committed bf34557

added an answer for problem 3

Comments (0)

Files changed (1)

python/3/prime_factorization.py

+#!/usr/bin/env python
+# -*- coding: utf-8 -*-
+
+def sieve_of_eratosthenes(max_num):
+    """
+    >>> sieve_of_eratosthenes(20)
+    [2, 3, 5, 7, 11, 13, 17, 19]
+    """
+    def hurui(s, p):
+        p.append(s.pop(0))
+        for i, num in enumerate(s):
+            if num % p[-1] == 0:
+                s.pop(i)
+    n = 2
+    prime = []
+    search = range(n, max_num + 1)
+    while not prime or prime[-1] ** 2 < search[-1]:
+        hurui(search, prime)
+    prime += search
+    return prime
+
+def prime_factorization(max_num):
+    """
+    >>> prime_factorization(13195)
+    [5, 7, 13, 29]
+    >>> prime_factorization(600851475143)
+    [71, 839, 1471, 6857]
+    """
+    from math import sqrt
+    _prime_max = int(sqrt(max_num))
+    prime = sieve_of_eratosthenes(_prime_max)
+    answer = []
+    div = max_num
+    for i in prime:
+        if div % i == 0:
+            div /= i
+            answer.append(i)
+    return answer