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 もあるのでそちらを見ながらやると捗ると思います。