[Python] How to get divisors of natural numbers at high speed
Introduction
Thank you for reading this article! !! This is ** Nakazon **, who made his programming debut in June 2020!
It is my daily routine to solve at least 5 AtCorder A-D questions.
In my article, from the perspective of a programming beginner, Learning and hardships discovered through daily routines I would like to tell you what I was happy about.
I will try to make the article learning for the same beginners! Advanced people watch with warm eyes and We look forward to your positive wisdom and advice!
Let's move on to today's content! !!
problem
Click here for the issues that led to today's learning
C - Walk on Multiplication Table https://atcoder.jp/contests/abc144/tasks/abc144_c
Considering N = 10 in the example, there are two candidates for i and j, (1, 10) and (2, 5). Consider the combination of i and j that satisfies N = i * j with the smallest i + j. Then, when I thought, "Let's get the divisor!" I fall into the state of "What? What should I do?" .. .. Lol
This is how you get the divisor of the natural number N! !!
Since N is a maximum of 10 ** 12, it is not possible to search all from 1 with a for statement. It takes too much time, so you need to devise it.
qiita.rb
N = int(input())
divisors = []
for i in range(1, int(N**0.5)+1):
if N % i == 0:
divisors.append(i)
if i != N // i:
divisors.append(N//i)
divisors.sort()
If you search to √N (the turning point of the divisor) like this The point is that you can get all the divisors.
Finally
I want to be a person who notices with such an algorithm element. It ’s amazing to notice
Recommended Posts