会社で少し盛り上がった Project Euler をやってみる 005

Problem 005

2520 は 1 から 10 の数字の全ての整数で割り切れる数字であり, そのような数字の中では最小の値である.
では, 1 から 20 までの整数全てで割り切れる数字の中で最小の正の数はいくらになるか.

---

Answer 005 (Python)

class Problem5:

    NUM = 20
    PRIME = []

    def main(self):
        answer = 1
        for i in range(2, self.NUM + 1):
            primeList = self.primeFactorize(i)
            if len(set(primeList)) == 1:
                answer *= primeList[0]
        print(answer)

    def primeFactorize(self, num):
        data = []
        i = 1
        while(i < num ** (1/2)):
            i += 1
            if i in self.PRIME:
                pass
            elif self.isPrime(i):
                self.PRIME.append(i)
            else:
                continue
            if num == i:
                break
            if num % i == 0:
                data.append(i)
                num //= i
                i -= 1
        data.append(num)
        return data

    def isPrime(self, num):
        for i in self.PRIME:
            if i > num ** (1/2):
                return True
            if num % i == 0:
                return False
        return True


if __name__ == '__main__':
    p = Problem5()
    p.main()

---

(参考) Project Euler とは

Project Euler はプログラミングで数学の問題を解くサイトです。問題は600問以上あるので、勉強に使うのも良し、楽しむのも良しです。

サイトに登録すれば、解答を submit することができ、その場であっているか判定してくれます。

また、問題だけであれば、日本語に翻訳された Wiki もあるのでそちらを見ながらやると捗ると思います。

Project Euler(日本語訳)