Is there any way to increase the performance of my python code without using threads/processes?

Question

I am trying to do the Euler Problems, and I am stuck on the Largest Prime Factor. I know how to work it out, but I am going about it in a brute-force manner. The files below are the two files in my project; prime.py with the is_prime_number() function, and app.py with the main() functionality.

Prime.py

import math


def is_prime_number(number):
    if number % 2 == 0:
        return False
    root_of_number = math.ceil(math.sqrt(number))
    for i in range(3, root_of_number + 1, 2):
        if number % i == 0:
            return False
    return True

App.py

# The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600851475143?

from prime import is_prime_number

def main():
    number = int(input("Please enter an integer: "))
    largest_prime_factor = 0

    for i in range(1, number + 1):
        if is_prime_number(i):
            if number % i == 0:
                if i > largest_prime_factor:
                    largest_prime_factor = i
        if i % 1000000 == 0:
            print(i)
    print(f"Largest prime factor of {number}: {largest_prime_factor}")

if __name__ == "__main__":
    main()

I am relatively new to programming, and am using Python because I have tried using other more efficient languages like Rust but have ran into countless errors because I do not know them as well. Are there any easy optimisations I am missing from my code? It is logging "i" every 1000000, and each log takes around 5 seconds. At this rate, if the logging keeps at this rate it will take around 13.9 hours. But I'm guessing it will slow down as the numbers get larger.

Also I know there are probably more efficient ways to approach this problem instead of brute forcing it, but I am not very knowledgeable in maths and am just having fun learning programming! :)

I don't think your ```is_prime_number``` function is correct. ```is_prime_number(8.5)``` is ```True``` and ```is_prime_number(2)``` is ```False``` — Hugh Mungus, Jul 18 '22 at 11:39
If you try all possible divisors starting from 2 (which you do) , and try each one as many times as possible (which you don't), there is no need to check that they are prime, as they necessarily are. As another improvement, you can use an efficient primes generator rather than testing any possible number. See [this question with excellent answers](https://stackoverflow.com/questions/2211990/how-to-implement-an-efficient-infinite-generator-of-prime-numbers-in-python). Anyway, you should really have a look at some more maths when working on such problems. — Thierry Lathuille, Jul 18 '22 at 11:40
@HughMungus Primality tests are only supposed to be used on integers, not floats. But you're right about 2. — Thierry Lathuille, Jul 18 '22 at 11:42
@HughMungus great name by the way! xD Thank you for that, I forgot to check for 2! — figgyfarts, Jul 18 '22 at 11:49
@ThierryLathuille I'm not quite sure I understand what you mean in your first sentence. But as for the second, I will look into that answer for a more efficient prime number generator. Thank you! :) — figgyfarts, Jul 18 '22 at 11:53

score 3 · Answer 1 · answered Jul 18 '22 at 12:46

You can use numba to JIT your current functions, which results in significant speed improvements (I've changed it to use numpy for ceil and sqrt as it is slightly faster than using math):

import numpy as np
import numba as nb

@nb.njit
def is_prime_number(number):
    if number % 2 == 0:
        return False
    root_of_number = np.ceil(np.sqrt(number))
    for i in range(3, root_of_number + 1, 2):
        if number % i == 0:
            return False
    return True

@nb.njit
def main(number):
    largest_prime_factor = 0

    for i in range(1, number + 1):
        if is_prime_number(i):
            if number % i == 0:
                if i > largest_prime_factor:
                    largest_prime_factor = i
        if i % 1000000 == 0:
            print(i)
    print(f"Largest prime factor of {number}: {largest_prime_factor}")

Timings:

%timeit main_op(7919)
%timeit main(7919)

Output:

3.83 ms ± 36.1 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
74.3 µs ± 245 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)

thank you for this solution! I will try to try it out when I get home :) — figgyfarts, Jul 18 '22 at 12:49

score 1 · Accepted Answer · answered Jul 18 '22 at 12:45

Also, for starters, you dont need to check all numbers up to "number+1". It is sufficient to test all numbers up to int(sqrt(number))+1. If you find a prime number, you divide your original number by that and repeat (recursively). At the end of this recursion, you will be left with some number which is itself prime and there will be no divisor found until sqrt(N). If that is the case, the number itself is a prime. I think with this method you will find primes quicker. E.g. for 3x7x7, you will just need 2+4+4 steps, instead of going through all the numbers. The last prime in the recursion should also be the largest prime factor, if I am not mistaken.

About code efficiency: Generally one should try to avoid for loops in python. I recommend you to look into e.g. the primefac module. I think you can get the full prime factorization of a number n by primefac.primefac(n) and then you can just pick its maximum (I am not too familiar with this module tho.)

thank you for your comment of only having to go up to sqrt of the number! — figgyfarts, Jul 18 '22 at 12:48
Omg just tried adding the square root to the code, and that alone gives me the answer almost immediately! Thank you so much!! — figgyfarts, Jul 18 '22 at 13:38

score 1 · Answer 3 · answered Jul 18 '22 at 13:06

Okay so I just improvised some code, I guess this hould do the trick. I have not yet thoroughly tested it, but I think it should be quite a bit quicker than your original code. I would be glad for any kind of feedback. And as I said, I think the fastest solution would be to use libraries instead of this python-style loops. But its a cool program for educative purposes I think. Hope this helps. Cheers!

import numpy as np

def main():
    number_original = int(input("Please enter an integer: "))
    number = 1*number_original
    largest_prime_factor = 0

    def Iteration(number):
        for i in range(2, int(np.sqrt(number))+1):
            if number % i == 0:
                return int(i),"NotDone"
        return int(number),"Done"

    Status = "NotDone"
    largest_prime_factor = 1

    while(Status == "NotDone"):

        number = number/largest_prime_factor
        largest_prime_factor,Status = Iteration(number)


    print(f"Largest prime factor of {number_original}: {largest_prime_factor}")

if __name__ == "__main__":
    main()

thank you for another great reply! I will try to look into this when I get home today! :) — figgyfarts, Jul 18 '22 at 13:09
This is ~10 times faster for the example of 7919 mentioned above, but it is expected that the speedup is even more significant for non-prime-numbers. Also, you can use numba to speed up the above function even further if you like. But I think this should suffice for starters. Feel free to ask about more details anytime ;) — Ritteraxt, Jul 18 '22 at 13:12

Is there any way to increase the performance of my python code without using threads/processes?

3 Answers3