CODEWITHSUNDEEP
pythonprime-factoring
Wybe Turing
Wybe Turing

Reputation: 63

prime factors for large numbers

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)

Upvotes: 3

Views: 331

Answers (1)

Deepak Saini
Deepak Saini

Reputation: 2900

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.

Upvotes: 3

Related Questions