파이썬 알고리즘(소수찾기 에라토스 테네스 체)

https://www.acmicpc.net/problem/11653

import sys
import math
input = sys.stdin.readline

N = int(input())
# 에라토스 테네스의 채 로 소수들을 찾는다.
def prime_num(n):
    arr = [True]*(n+1)
    prime_arr = []

    for i in range(2, int(math.sqrt(n)+1)):
        if arr[i]==True:
            j=2
            while(i*j)<=n:
                arr[i*j]=False
                j+=1
    
    for i in range(2,len(arr)):
        if arr[i] :
            prime_arr.append(i)

    return prime_arr

prime_Arr = prime_num(N)

for i in prime_Arr:
    while 1:
        A = N%i
        if A:
            break
        else:
            N = N//i
            print(i)

key point :

특정 수 N의 약수들을 일렬로 나열했을 때 그 중 가운데의 수를 중심으로 약수가 대칭된다.

따라서 N의 약수를 찾고 싶을때 반쪽을 기준으로 하면 다른쪽 약수를 알 수 있다.