pythonprime-factoring

Why is code for prime numbers not working for the number 10?


I am trying to write a code in python to find all prime numbers of a number. My problem is that with this line of code it does not work to return the prime numbers of 10, the list only returns 2. Now I adapted this code from this page https://www.geeksforgeeks.org/prime-factor/ as I want to make my factors come out as a list.

The code from that website works for the number 10, however I do not understand why it does not work for number 10 when I run my own slightly modified version of it.

I have tried to +10 at the end of my range function, instead of a +1 and this does solve the problem, however I am still unsure as to why I even have a problem in the first place. Secondly, will the +10 work for all numbers with no error? In theory it should as I should only have factors unto square root of n, but I am not sure again. Lastly, if if the +10 does work, won't that make the code run slower as it will iterate through unneeded loops, how can I improve the speed?

This is my code that I used.

import math

def primefact():
    n = int(input('What is your number?:'))
    prime_factors = []
    while n % 2 == 0: # Checks if number is divisible by 2
        prime_factors.append(2) #repeats it until n is no longer divisible by 2
        n = n / 2 
    for i in range(3, int(math.sqrt(n)) + 1, 2): # Testing for odd factors
        while n % i == 0: 
            prime_factors.append(i)
            n = n / i
    print(prime_factors)
    return 

primefact()

Solution

  • Here's a piece of code that I wrote:

    from numpy import mod, int0, sqrt, add, multiply, subtract, greater, equal, less, not_equal, floor_divide
    class findFactors:
    def __init__(self, n):
        self.primeFactorize(n)
        
    def primeFactorize(self, n):
        factors = self.findFactors(n)
        self.factors = factors
        primeFactors = []
        xprimeFactors = []
        for factor in factors:
            if prime(factor).isPrime:
                primeFactors.append(factor)
        ntf = n
        nprime = 0
        while not_equal(ntf, 1):
            while equal(mod(ntf, primeFactors[nprime]), 0):
                ntf = floor_divide(ntf, primeFactors[nprime])
                xprimeFactors.append(primeFactors[nprime])
            nprime = add(nprime, 1)
        self.primeFactors = primeFactors
        self.extendedPrimeFactors = xprimeFactors
    
    def findFactors(self, number):
        if prime(number).isPrime: return [1, number]
        factors = []
        s = int0(sqrt(float(number)))
        for v in range(1, add(s, 1)):
            if equal(mod(number, v), 0):
                factors.append(int(v))
                factors.append(int(floor_divide(number, v)))
        factors.sort()
        return factors
    
    class prime:
    def __init__(self, n):
        self.isPrime = self.verify(n)
    
    def verify(self, n):
        if less(n, 2):
            return False
        if less(n, 4):
            return True
        if not n & 1 or equal(mod(n, 3), 0):
            return False
        s = int0(sqrt(float(n)))
        for k in range(1, add(s, 1)):
            mul = multiply(6, k)
            p = add(mul, 1)
            m = subtract(mul, 1)
            if greater(m, s):
                return True
            if equal(mod(n, p), 0) or equal(mod(n, m), 0):
                return False
    

    Imagine func = findFactors(n)

    func.factors will returns a list with all the factors of the number n,

    func.extendedPrimeFactors will return a list with the prime factorization of the number,

    func.primeFactors will return a list with the primes appearing only once instead of x times

    also, there's a really fast prime checker down there. (Prime checker usage: prime(n).isPrime )