Skip to content

Instantly share code, notes, and snippets.

@Hayao0819
Created September 24, 2023 14:14
Show Gist options
  • Save Hayao0819/03672faa12fffd333f47a995a991f923 to your computer and use it in GitHub Desktop.
Save Hayao0819/03672faa12fffd333f47a995a991f923 to your computer and use it in GitHub Desktop.
素因数分解
#!/usr/bin/env python3
import math
import sys
def main() -> int:
if len(sys.argv) != 2:
print("error")
return 1
num:int = int(sys.argv[1])
primes:list[int]=factor(num)
print(primes)
print(str(num) + " = " + str(math.prod(primes)))
return 0
def factor(target:int) -> list[int] :
current:int = target # 割られる数の残り どんどん素数で割られて最終的に1になるはず
loop:int =2 # ループ用 最終的に√targetまで増加
primes:list[int]=[] # 素因数
while (current != 1 and loop < int(math.sqrt(target)) ): # ⇔ !(current == 1 || loop < √target)
print(loop)
if (current%loop == 0 ):
primes.append(loop)
current=current/loop
else:
loop+=1
return primes
if __name__ == "__main__":
sys.exit(main())
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment