Looking for the other half in the Kingdom of Mathematics: finding the sum of true factors of an integer, algorithm optimization solution to the timeout problem

The Kingdom of Mathematics looks for the other half, finds the sum of the true factors of an integer, and optimizes the algorithm to solve the timeout problem.

(This note is suitable for coders who are familiar with python strings and lists)


[The details of learning are a joyful process]

  • Python official website: python cutting edge. Unfortunately it’s the original English version. So, I want to practice English reading. “>https://www.python.org/

  • Free: Free for big names “Bible” tutorial “ python complete self-study tutorial” is not just as simple as the basics…
    Address: https://lqpybook.readthedocs.io/

Self-study is not a mysterious thing, a person The time spent studying by oneself in a lifetime is always longer than the time spent studying in school, and the time without a teacher is always longer than the time with a teacher.
— Hua Luogeng

  • My CSDN homepage, My HOT blog, My Python learning personal memo
  • Highly recommended for good articles, Lao Qi Classroom


It is better to chase the wind than to wait for it...


Looking for the other half in the Kingdom of Mathematics


Warm-hearted Xiaonan


(Find the sum of the true factors of an integer)

Quality score of this article:


【 96 】
This article address:
https://blog.csdn.net/m0_57158496/article/details/133635207

CSDN quality score query entrance: http://www.csdn.net/qc


Directory

  • ◆?Warm-hearted Xiaonan
    • 1. Topic description
    • 2. Algorithm analysis
      • 2.1 Conventional full loop traversal algorithm
      • 2.2 Square root traversal to integer square root optimization algorithm
    • 3. Complete source code

◆?Warm-hearted Xiaonan

1. Title description

  • Screenshot of question description

[The question comes from the CSDN Q&A community question “Finding the Other Half in the Kingdom of Mathematics”]


Back to table of contents

2. Algorithm analysis

Code optimization is not enough to solve the timeout problem. After careful consideration, I found a way that can greatly reduce the number of traversals: Starting from 2, every time a number is divisible by the traversal, the corresponding number will be accumulated two factors of For the accumulated factors, the factors of the integers have been found at this point in the traversal; it is worth noting that 1 is always the true factor of the integer number and is not accumulated during the traversal. In addition, if the integer has an integer square root, the same factor is added during the loop traversal. (square root). So, in the optimization algorithm code, the return statement uses a ternary operation to return the final result according to the situation. In “special” situations(When the integer n has an integer square root)The median value should be subtracted below.

  • Sample question test

2.1 Conventional full loop traversal algorithm

  • Screenshot of code running effect

Conventional analytical algorithm can also be written as a conventional for loop. The loop writing method is slightly less efficient than the analytical method, but the difference is very small and can almost be ignored. But the analytical way of writing is simple.

code

def sum_factor(n): # Conventional analytical algorithm can also be written as a conventional for loop.
    return sum([i for i in range(1, n) if not n%i])


Back to table of contents

2.2 Square root traversal to integer square root optimization algorithm

  • Screenshot of code running effect

code

def sum_factor(n): # Optimize the square root traversal to square root algorithm.
    result = 0
    m = int(sqrt(n))
    
    for i in range(2, m + 1):
        
        if not n%i:
            print(i, n//i) # Statement for program debugging.
            result + = i + n//i

    return result + 1 if sqrt(n)%1 else result + 1 - m


Back to table of contents

3. Complete source code

(The source code is long, click here to skip the source code)

#!/sur/bin/nve python
# coding: utf-8
from time import time
from math import sqrt

def sum_factor(n): # Conventional analytical algorithm can also be written as a conventional for loop.
    return sum([i for i in range(1, n) if not n%i])


def sum_factor(n): # Optimize the square root traversal to square root algorithm.
    result = 0
    m = int(sqrt(n))
    
    for i in range(2, m + 1):
        
        if not n%i:
            print(i, n//i)
            result + = i + n//i

    return result + 1 if sqrt(n)%1 else result + 1 - m


def main(t, *nums): # Main program for calculating multiple integers n.
    
    for i in nums:
        print(sum_factor(i))


if __name__ == '__main__':
    n = input('\
Input:\
').strip()

    if not n:
        s ='''3
2
10
20'''
        print(s)
        n = s[0]
    else:
        s = ''
        for i in range(int(n)):
            s + = '\
' + input().strip()
    print('\
Output: ')
    start = time()
    main(int(n), *map(int, s.split('\
')[1:]))
    print(f"\
Program time: {<!-- -->time()-start}s\
")


Back to top


Previous article: “What’s the stupidest code I’ve ever written?” Activity Essay Collection(“What’s the stupidest code I’ve ever written?” “Activity essay collection. To be honest, I don’t think I have ever written the stupidest code! It’s just so childish and cute)
Next article:?

My HOT blog:

A total of 241 blog post notes were collected this time, with a total reading volume of 40.66w and an average reading volume of 1687. 16 blog post note index links with a reading volume of no less than 4,000 have been generated. Data collection was completed at 2023-10-05 22:53:15, taking 4 minutes and 12.96 seconds.

  1. First experience of ChatGPT domestic mirror site: chat, Python code generation, etc.
    ( 59106 reading)
    Blog address: https://blog.csdn.net/m0_57158496/article/details/129035387
    Like: 125 Dislike: 0 Collection: 796 Reward: 0 Comment: 71
    This blog post was first published on 2023-02-14 23:46:33 and modified at the latest on 2023-07-03 05:50:55.
  2. The magic code that changes the nickname of QQ group
    ( 58033 reading)
    Blog address: https://blog.csdn.net/m0_57158496/article/details/122566500
    Like: 24 Dislike: 0 Collection: 83 Reward: 0 Comment: 17
    This blog post was first published at 2022-01-18 19:15:08 and was modified at the latest at 2022-01-20 07:56:47.
  3. pandas data type DataFrame
    ( 9148 reading)
    Blog address: https://blog.csdn.net/m0_57158496/article/details/124525814
    Like: 6 Dislike: 0 Collection: 31 Reward: 0 Comment: 0
    This blog post was first published on 2022-05-01 13:20:17 and modified at the latest on 2022-05-08 08:46:13.
  4. Personal information extraction (string)
    ( 7186 Reading)
    Blog address: https://blog.csdn.net/m0_57158496/article/details/124244618
    Like: 1 Dislike: 0 Collection: 13 Reward: 0 Comment: 0
    This blog post was first published on 2022-04-18 11:07:12 and modified at the latest on 2022-04-20 13:17:54.
  5. Roman Numeral Converter | Roman Numeral Generator
    ( 7021 Reading)
    Blog address: https://blog.csdn.net/m0_57158496/article/details/122592047
    Like: 0 Dislike: 0 Collection: 1 Reward: 0 Comment: 0
    This blog post was first published at 2022-01-19 23:26:42 and was modified at the latest at 2022-01-21 18:37:46.
  6. Python string displayed in the center
    ( 6915 Reading)
    Blog address: https://blog.csdn.net/m0_57158496/article/details/122163023
    Like: 1 Dislike: 0 Collection: 7 Reward: 0 Comment: 1
    Notes for this blog
  7. 7 ways to implement reverse order (descending order) of Python lists
    ( 6902 Reading)
    Blog address: https://blog.csdn.net/m0_57158496/article/details/128271700
    Like: 5 Dislike: 0 Collection: 20 Reward: 0 Comment: 8
    This blog post was first published at 2022-12-11 23:54:15 and was modified at the latest at 2023-03-20 18:13:55.
  8. Recursive implementation and for implementation of Fibonacci sequence
    ( 5517 reads)
    Blog address: https://blog.csdn.net/m0_57158496/article/details/122355295
    Like: 4 Dislike: 0 Collection: 2 Reward: 0 Comment: 8
    Notes for this blog
  9. Exercise: String statistics (pit: fstring error report)
    ( 5094 reads)
    Blog address: https://blog.csdn.net/m0_57158496/article/details/121723096
    Like: 0 Dislike: 0 Collection: 1 Reward: 0 Comment: 0
    This blog post was published at 2021-12-04 22:54:29.
  10. python clear screen
    ( 5071 reads)
    Blog address: https://blog.csdn.net/m0_57158496/article/details/120762101
    Like: 0 Dislike: 0 Collection: 8 Reward: 0 Comment: 0
    Notes for this blog
  11. Carriage return, line feed, and carriage return and line feed
    ( 5068 reads)
    Blog address: https://blog.csdn.net/m0_57158496/article/details/123109488
    Like: 1 Dislike: 0 Collection: 2 Reward: 0 Comment: 0
    This blog post was first published at 2022-02-24 13:10:02 and modified at the latest at 2022-02-25 20:07:40.
  12. Exercise: Nim game (smart version/fool style? Man-machine battle)
    ( 4932 reads)
    Blog address: https://blog.csdn.net/m0_57158496/article/details/121645399
    Like: 14 Dislike: 0 Collection: 42 Reward: 0 Comment: 0
    Notes for this blog
  13. Password strength detector
    ( 4306 reads)
    Blog address: https://blog.csdn.net/m0_57158496/article/details/121739694
    Like: 1 Dislike: 0 Collection: 4 Reward: 0 Comment: 0
    This blog post was first published at 2021-12-06 09:08:25 and modified at the latest at 2022-11-27 09:39:39.
  14. Exercise: Generate 100 random positive integers
    ( 4255 reads)
    Blog address: https://blog.csdn.net/m0_57158496/article/details/122558220
    Like: 1 Dislike: 0 Collection: 6 Reward: 0 Comment: 0
    This blog post was first published at 2022-01-18 13:31:36 and was modified at the latest at 2022-01-20 07:58:12.
  15. Roman numeral converter (implemented using the modulus of the value of the Roman numeral construction element)
    ( 4143 reads)
    Blog address: https://blog.csdn.net/m0_57158496/article/details/122608526
    Like: 0 Dislike: 0 Collection: 0 Reward: 0 Comment: 0
    This blog post was first published at 2022-01-20 19:38:12 and modified at the latest at 2022-01-21 18:32:02.
  16. My Python.color() (Python color printing control)
    ( 4128 reads)
    Blog address: https://blog.csdn.net/m0_57158496/article/details/123194259
    Like: 2 Dislike: 0 Collection: 8 Reward: 0 Comment: 0
    This blog post was first published on 2022-02-28 22:46:21 and modified at the latest on 2022-03-03 10:30:03.


Recommendation conditions
Reads exceeded 3,000


(For more hot blogs, please click on the blue text to jump to read)


Back to top



Lao Qi comic avatar

Excellent articles:

  • Recommended articles: Qi Wei Shu Manuscript “Python Complete Self-Study Tutorial” FreeSerial(has been completed and compiled into a book, and there is also a PDF version for permanent sharing on Baidu Netdisk, Click Jump for free download.)
  • Three major features of OPP: property in encapsulation
  • Understanding python’ through built-in objects
  • regular expression
  • The role of “*” in python
  • Python complete self-study manual
  • walrus operator
  • `!=` in Python is different from `is not`
  • The right way to learn programming

Source: Lao Qi Classroom


Back to top

◆ Python Getting Started Guide[Python 3.6.3]

Highly recommended for good articles:

  • A high-quality creator in the full-stack field – [Hanlao](still a student in a domestic university) blog post “Non-technical article – about English and how to speak correctly “Asking questions”, “English” and “Being able to ask questions” are two powerful tools for learning programming.
  • [Applicable fields of 8 major programming languages] Don’t rush to choose linguistic programming first, first look at what they can do
  • Good habits of reliable programmers
  • The three major elements of “Function function, end condition, and function equivalence” in the high-quality and good article by the boss Shuaidi will help you understand recursion.

CSDN Practical Tips Blog:

  • 8 Python practical tips that are extremely useful
  • python ignore warning
  • Python code writing specifications
  • Python’s docstring specification (standard way of writing documentation)