python - Optimising Factoring Program -


this factorising code used find factors of number after 7 digits, program begins slow down.

so wondering if there method of optimising program allow factorise numbers faster.

number = int(input("input whole number here?\n")) factors = [1]  def factorization():     global factors     in range(1 , number):         factor = (number/i)         try:             factorint = int(number/i)             if factorint == factor:                 factors.append(factorint)         except valueerror:             pass   factorization() print(factors) 

the effective optimization noting when number has non trivial factors, , smallest of them smaller square root of number, , there no need continue looping past square root.

indeed, let smallest factor m. have n = m.p , other factor such p >= m. if m > √n, m.p >= n, contradiction.


note optimization speeds-up processing of prime numbers (for composite ones, search stops before √n anyway). density of primes , fact n larger √n make abolutely worth.


another optimization noting smallest divisor must prime, , can use stored table of primes. (there less 51 million primes below 1 billion.) speedup less noticeable.


Comments

Popular posts from this blog

resizing Telegram inline keyboard -

command line - How can a Python program background itself? -

php - "cURL error 28: Resolving timed out" on Wordpress on Azure App Service on Linux -