When finding the prime factors of a number some numbers work but others dont

Question

When testing numbers some work for example 48, but others don't. I'm not sure what the best way to approach finding all the factors of a number.

Prime Factorization

def find_primes(n): 
    factors = []
    i = 2
    if n == 0:
        return 0              
    if n == 1:
        return 1                
    if n >= 2:
        while n % i == 0:
            next_n = n / i
            factors.append(i)
            n = next_n 
            if n % i != 0:
                i += 1
                continue
            elif i == n:
                break
    if len(factors) == 0:
        return "{} is a prime number.\n".format(initial_n)
    else:
        return "The prime factors of {} are: {}\n".format(initial_n, factors)


n = int(input("Enter a number to find all the Prime Factors:"))
initial_n = n
print('\n')
print(find_primes(n))

I am expecting to get a list of all the factors of a number.

The while-loop is left (or never entered) if an i can't divide n at least once regardless if greater values for i could. — Michael Butscher, May 28 '19 at 01:03

score 0 · Answer 1 · answered May 28 '19 at 01:29

0

I changed your code and now it works for all natural numbers:

def find_primes(n): 
    factors = []
    i = 2
    if n == 0:
        return 0
    if n == 1:
        return 1
    if n >= 2:
        while i * i <= n:
            while n % i == 0:
                factors.append(i)
                n = n // i
            i += 1
    if n > 1:
        factors.append(n)
    if len(factors) == 1:
        return "{} is a prime number.\n".format(initial_n)
    else:
        return "The prime factors of {} are: {}\n".format(initial_n, factors)


n = int(input("Enter a number to find all the Prime Factors:"))
initial_n = n
print('\n')
print(find_primes(n))

answered May 28 '19 at 01:29

Erfan Alimohammadi

460
3
9

thanks it works but i have a couple questions. Why did you use "while i * I <= n" in the first while statement? Also what is the point of the final if statement, "if n > 1" – parth May 28 '19 at 02:00
@parth if n is a prime number, it has at least one divisor not greater than sqrt(n), so "while i * i <= n" will find that; otherwise n will be never divided by anything and we will check this by "n > 1". – Erfan Alimohammadi May 28 '19 at 03:16
Actually, using "i * i <= n" makes the algorithm faster in comparison to use "i <= n". It makes an O(n) algorithm to an O(sqrt(n)) one. – Erfan Alimohammadi May 28 '19 at 03:30

Shiping · Answer 2 · 2019-05-28T01:51:46.603

def find_primes(n):
    factors = []
    i = 2
    if n == 0:
        return 0
    if n == 1:
        return 1
    while i <= n:
        if n % i == 0:
            factors.append(i)
            n /= i
        else:
            i += 1
    if len(factors) == 0:
        return "{} is a prime number.\n".format(initial_n)
    else:
        return "The prime factors of {} are: {}\n".format(initial_n, factors)


n = int(input("Enter a number to find all the Prime Factors:"))
initial_n = n
print('\n')
print(find_primes(n))

score 0 · Accepted Answer · answered May 28 '19 at 02:09

The function to calculate the prime factors below is much simpler than the one above. The rest is just sanity checking of user input.

###########################################################
#Main function to calculate prime factors
def find_prime_factors(n):
    factors = []
    p = 2
    while n > p ** 2:
        if n % p == 0:
            factors.append(p)
            n //= p
        else:
            p += 1
    factors.append(n)
    return factors
###########################################################

# Get User input
n = input('Enter a number to find all the Prime Factors: ') 

# Check if the entered value is a number
while not n.isnumeric():
    print('Entered number was not numeric.')
    n = input('Enter a NUMBER to find all the Prime Factors: ') 

# Check the entered value is greater than one (1)
# Prime Factor check happens on only positive numbers that are greater than one (1)

while int(n) < 2:
    print("Please enter a positive number that is greater than one (1).")
    n = input('Enter a NUMBER to find all the Prime Factors: ') 

#Python 3.7 string formating
print(f'The prime factor(s) of {n}: {find_prime_factors(int(n))} ')

When finding the prime factors of a number some numbers work but others dont

Prime Factorization

3 Answers3