prime factors for large numbers

Question

I wrote this to determine the largest prime factor of any given number. It works well for numbers with less than 9 digits but behaves in an indefinite manner when the number of digits goes beyond nine. How can I optimize it?

This function determines if a number is a prime number

def is_prime(x):
    u = 1
    i = 2
    while i < x:
        if x%i == 0:
            u = 0
            break
        else:
            i = i+1
    return u

This function determines if a number is a prime factor of another

def detprime(x,y):
    if x%y == 0:
        if (is_prime(y)):
            return 1
        else:
            return 0
    else:
        return 0

This section checks for all the prime factors of a given number, stores them in a list, and returns the largest value

def functionFinal(x):
    import math
    factors = []
    y = x//2
    for i in range(1,y):
        if detprime(x,i) == 1:
            factors.append(i)
    y = len(factors)
    print(factors[y-1])

import time
start_time = time.process_time()
print("Enter a number")
num = int(input())
functionFinal(num)

print(time.process_time()-start_time)

You could fasten your prime number checker with function explained in [this answer](https://stackoverflow.com/a/18833870/7918714) — Filip Młynarski, Nov 23 '18 at 12:18

score 3 · Accepted Answer · answered Nov 23 '18 at 12:45

You can improve your code by having a more efficient function to check primality. Apart form that, you need to only store the last element of your list factors. Also, you can increase the speed by JIT compiling the function and using parallelisation. In the code below, I use numba.

import math
import numba as nb

@nb.njit(cache=True)
def is_prime(n):
    if n % 2 == 0 and n > 2: 
        return 0
    for i in range(3, int(math.sqrt(n)) + 1, 2):
        if n % i == 0:
            return 0
    return 1

@nb.njit(cache=True)
def detprime(x, y):
    if x % y == 0:
        if (is_prime(y)):
            return 1
        else:
            return 0
    else:
        return 0

@nb.njit(parallel=True)
def functionFinal(x):
    factors = [1]
    y = x // 2
    for i in nb.prange(1, y): # check in parallel
        if detprime(x, i) == 1:
            factors[-1] = i

    return factors[-1]

So, that

functionFinal(234675684)

has the performance comparison,

Your code : 21.490s

Numba version (without parallel) : 0.919s

Numba version (with parallel) : 0.580s

HTH.

Wow! What an improvement. Thanks. – Wybe Turing Nov 23 '18 at 14:36 — Wybe Turing, Nov 23 '18 at 14:36

prime factors for large numbers

This function determines if a number is a prime number

This function determines if a number is a prime factor of another

This section checks for all the prime factors of a given number, stores them in a list, and returns the largest value

1 Answers1