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
