prime factorization python

1import math
2
3
4def primeFactors(n):
5    # no of even divisibility
6    while n % 2 == 0:
7        print(2)
8        n = n / 2
9    # n reduces to become odd
10    for i in range(3, int(math.sqrt(n)) + 1, 2):
11        # while i divides n
12        while n % i == 0:
13            print(i)
14            n = n / i
15    # if n is a prime
16    if n > 2:
17        print(n)
18
19
20primeFactors(256)

1# There is no quick way to calculate the prime factors of a number.
2# In fact, prime factorization is so famously hard that it's what puts the "asymmetric" in asymmetric RSA encryption.
3# 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.
4
5def factors(num):
6        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.
7        pdict = {}
8        for p in ps:
9                if p <= num:
10                        while (num / p).is_integer():
11                                if str(p) in pdict:
12                                        pdict[str(p)] += 1
13                                else:
14                                        pdict[str(p)] = 1
15                                num /= p
16                if num == 1: break
17        return pdict
18
19# Returns a dictionary in the form {"base": "exponent"}