Python Finding Prime Factors

Prime factorization - list

A simple trial division:

def primes(n):
    primfac = []
    d = 2
    while d*d <= n:
        while (n % d) == 0:
            primfac.append(d)  # supposing you want multiple factors repeated
            n //= d
        d += 1
    if n > 1:
       primfac.append(n)
    return primfac

with O(sqrt(n)) complexity (worst case). You can easily improve it by special-casing 2 and looping only over odd d (or special-casing more small primes and looping over fewer possible divisors).

I have a Python list of the prime factors of a number. How do I (pythonically) find all the factors?

Instead of a list of exponents, consider simply repeating each prime factor by the number of times it is a factor. After that, working on the resulting primefactors list-with-repetitions, itertools.combinations does just what you need -- you'll just require the combinations of length 2 to len(primefactors) - 1 items included (the combinations of just one are the prime factors, that of all of them will be the original number -- if you want those too, just use range(1, len(primefactors) + 1) instead of the range(2, len(primefactors)) which my main suggestion would use).

There will be repetitions in the results (e.g., 6 will appear twice as a factor of 12, since the latter's primefactors will be [2, 2, 3]) and they can of course be weeded out in the usual ways (i.e. sorted(set(results)) for example).

To compute primefactors given listOfAllPrimes, consider for example:

def getprimefactors(n):
    primefactors = []
    primeind = 0
    p = listOfAllPrimes[primeind]
    while p <= n:
        if n % p == 0:
            primefactors.append(p)
            n //= p
        else:
            primeind += 1
            p = listOfAllPrimes[primeind]
    return primefactors

Prime factors, help understand the use of square root

It's simple arithmetic. If r is the square root of n, then r * r == n. If you multiply r by anything larger than it, the result will be larger than n. So there can't be any other prime factor larger than r.

So there's no point in continuing the loop past the square root, since it can never find anything there.

Product of prime factors of a number, less than that number

You base all your range limits on just min(F). Let's customize each to the log(a, factor) to reduce the cases:

from math import ceil, log, prod
from itertools import product

a = 60
F = [2, 3, 5]

ranges = [range(0, ceil(log(a, factor))) for factor in F]

C = []

for powers in product(*ranges):
    if prod(F[i] ** power for i, power in enumerate(powers)) < a:
        C.append(powers)

print(C)

By my measure, your code generates 216 test cases to come up with 25 results, but the above code only generates 1/3 of those test cases.

How to compare numbers for highest number of prime factors in Python?

Using an algorithm from this answer I wrote one to solve your problem.

def prime_factors(n):
    i = 2
    factors = []
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            factors.append(i)
    if n > 1:
        factors.append(n)
    return factors

input_numbers = []
for i in range(0,10):
    input_numbers.append(int(input()))

highest_num = 0
highest_amount = 1
for num in input_numbers:
    factors = list(dict.fromkeys(prime_factors(num)))
    factors_amount = len(factors)
    if factors_amount > highest_amount:
        highest_num = num
        highest_amount = factors_amount
    elif factors_amount == highest_amount:
        if num > highest_num:
            highest_num = num

print(highest_num,highest_amount)

---

Related Topics