Member Avatar for KrazyKitsune

Title says all. I need to make a code that gives the prime factorization of a number and put them in a (this is important) a list.

  • 4 Contributors
  • 3 Replies
  • 192 Views
  • 1 Year Discussion Span
  • Latest Post Latest Post by TrustyTony

Dani AI

Generated

A compact, Python-3-friendly approach that returns the prime factors as a list (with multiplicity). This uses trial division but applies the 6k +/- 1 wheel (after removing factors 2 and 3) so you avoid testing every integer; it implements the optimization suggested while keeping the code simpler than maintaining a next_prime helper (the next_prime in 's post was missing). 's idea of a helper test is fine, but you don't need a separate primality function if you divide factors out as you go.

import math

def prime_factors(n):
    "Return list of prime factors of integer n (multiplicity preserved)."
    if not isinstance(n, int):
        raise TypeError("n must be an integer")
    if n == 0:
        raise ValueError("cannot factorize 0")
    factors = []
    if n < 0:
        factors.append(-1)
        n = -n

    while n % 2 == 0:
        factors.append(2); n //= 2
    while n % 3 == 0:
        factors.append(3); n //= 3

    i = 5
    while i <= math.isqrt(n):
        while n % i == 0:
            factors.append(i); n //= i
        while n % (i + 2) == 0:
            factors.append(i + 2); n //= (i + 2)
        i += 6

    if n > 1:
        factors.append(n)
    return factors

# example: prime_factors(360) -> [2, 2, 2, 3, 3, 5]

Notes and troubleshooting: use integer division (//) so Python 3 behavior is correct; return is an empty list for 1, [-1, ...] for negative inputs, and ValueError for 0. Complexity is roughly O(sqrt(n)) in the worst case; for very large inputs consider more advanced algorithms (Pollard Rho or library routines). This version avoids repeated primality checks and is easy to test and extend.

Recommended Answers

All 3 Replies

Member Avatar for cghtkh

Here is some code to help you, but you need to do some work.

# define your own function that check for prime
def isPrime(x):
    pass

def primeFactorization(num):
    
    pfactors = []
    while True:
          j = 2
          while j < num+1:
              if num%j==0 and isPrime(j):
                 num = num/j
                 pfactors.append(j)
                 break
              j+=1
          if num==1:
             break
    return pfactors
Member Avatar for eceisl

Title says all. I need to make a code that gives the prime factorization of a number and put them in a (this is important) a list.

def is_prime(num):
divisor=2
if(num==1):
return False
while(divisor<=num/2):
if(num%divisor==0):
return False
else:
divisor=divisor+1
return True

def print_prime_factors(num):
for i in range(2,num+1):
if(num==1):
break
while(num%i==0):
print (i)
num=num/i
i=next_prime(i)

I do not think that your code is working properly. Here is my code. You should call the last function.

Member Avatar for TrustyTony

You do not need to test all numbers neither test for prime as factorin wjile loop ensures prime. You can test for only valid prime candidates n * 6 +- 1 after testing with 2 and 3. BTW this is old solved thread and I do not know how much this post helps OP, make own thred with link to old one you read. !lso the function next_prime in your code does not exist.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.