You are viewing a single comment's thread. Return to all comments →
Python
Gets prime factors of each number from 1 to N and "adds them together"
#!/bin/python3 import sys import math def is_prime(n): if n % 2 == 0: return False if n < 9: return True if n % 3 == 0: return False r = int(n**0.5) f = 5 while f <= r: if n % f == 0: return False if n % (f + 2) == 0: return False f += 6 return True def primefactors(n): if is_prime(n): return {n: 1} factors = dict() while n % 2 == 0: if 2 in factors: factors[2] += 1 else: factors[2] = 1 n = n / 2 for i in range(3, int(math.sqrt(n))+1, 2): while n % i== 0: if i in factors: factors[i] += 1 else: factors[i] = 1 n = n / i if n > 2: factors[int(n)] = 1 return factors def add_to_factors_dict(d1, d2): for key, value in d2.items(): if key in d1: if value > d1[key]: d1[key] = value else: d1[key] = value return d1 t = int(input().strip()) for a0 in range(t): n = int(input().strip()) factors = dict() for i in range(2, n+1): prime_factors = primefactors(i) factors = add_to_factors_dict(factors, prime_factors) num = 1 for key, value in factors.items(): num *= pow(key, value) print(num)
Seems like cookies are disabled on this browser, please enable them to open this website
Project Euler #5: Smallest multiple
You are viewing a single comment's thread. Return to all comments →
Python
Gets prime factors of each number from 1 to N and "adds them together"