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! :)
CodePudding user response:
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)
CodePudding user response:
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.)