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! :)

Answer 1

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.)