Python
math
ProjectEuler

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

Problem 003

13195 の素因数は 5, 7, 13, 29 である.
600851475143 の素因数のうち最大のものを求めよ.

Answer 003 (Python)

(コメント欄でご指摘頂き、修正したものです)
修正前のものは下に残してあります。

class Problem3:

    NUM = 600851475143
    PRIME = []

    def main(self):
        i = 1
        while(i < self.NUM ** (1/2)):
            i += 1
            if i in self.PRIME:
                pass
            elif self.isPrime(i):
                self.PRIME.append(i)
            else:
                continue
            # 最後に割り切れて終わると答えが1になってしまうので以下2行追記
            # @shiracamus さんにご指摘頂きました
            if self.NUM == i:
                break
            if self.NUM % i == 0:
                self.NUM = self.NUM / i
                i = i - 1
        print(int(self.NUM))

    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 = Problem3()
    p.main()

修正前版

1種類の素因数しかない場合にうまく動作しない。
コメント欄で@shiracamusさんにご指摘頂き上記の修正版を用意しました。

class Problem3:

    NUM = 600851475143
    PRIME = set()

    def main(self):
        i = 2
        while(i < self.NUM ** (1/2)):
            if i not in self.PRIME and self.isPrime(i):
                self.PRIME.add(i)
            else:
                i += 1
                continue
            if self.NUM % i == 0:
                self.NUM = self.NUM / i
        print(int(self.NUM))

    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 = Problem3()
    p.main()

(参考) Project Euler とは

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

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

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

Project Euler(日本語訳)