prime factorization python
import math def primeFactors(n): # no of even divisibility while n % 2 == 0: print(2) n = n / 2 # n reduces to become odd for i in range(3, int(math.sqrt(n)) + 1, 2): # while i divides n while n % i == 0: print(i) n = n / i # if n is a prime if n > 2: print(n) primeFactors(256)
python prime factors
# There is no quick way to calculate the prime factors of a number. # In fact, prime factorization is so famously hard that it's what puts the "asymmetric" in asymmetric RSA encryption. # That being said, it can be sped up a little bit by using divisibility rules, like checking if the sum of the digits is divisible by 3. def factors(num): ps = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149] # Primes from https://primes.utm.edu/lists/small/10000.txt. Primes can also be generated by iterating through numbers and checking for factors, or by using a probabilistic test like Rabin-Miller. pdict = {} for p in ps: if p <= num: while (num / p).is_integer(): if str(p) in pdict: pdict[str(p)] += 1 else: pdict[str(p)] = 1 num /= p if num == 1: break return pdict # Returns a dictionary in the form {"base": "exponent"}
Copyright © 2021 Codeinu
Forgot your account's password or having trouble logging into your Account? Don't worry, we'll help you to get back your account. Enter your email address and we'll send you a recovery link to reset your password. If you are experiencing problems resetting your password contact us
