[python_파이썬]백준_11653번_소인수분해_풀이

공부하는허딩크 : https://www.youtube.com/live/JKVbtCm4CSM?feature=shared

일단 문제를 접했을때 쉬운 소수판별은 아닌거 같아서 노트에 필기를 시작했다.

1. 주어진 정수의 소인수들을 구한다.
     ㄴ 약수를 구한다.
     ㄴ 약수중에 소수의 숫자들만 별도로 리스트로 만든다.
2. 그 소인수들중에서 작은 수부터 계속 나눠서 마지막 정수가 1이 나올때까지 반복한다.
    ㄴ 여기 반복이 조금 헷갈렸지만 for문을 먼저 두고 소인수의 요소를 차례로 뽑아낸다
    ㄴ 첫번째 요소로 나눌때 나머지가 0이 될때마다 출력한다.
    ㄴ 두번째 요소로 나눌때 나머지가 0이 될때마다 출력한다.

<첫번째 작성 코드>

import sys

input = sys.stdin.readline

def isprime(N):

    if N <= 1:

        return False

    for i in range(2, int(N ** 0.5) + 1):

        if N % i == 0:

            return False

    return True

A = int(input())

answer = []

if A > 1:

    for i in range(2, A + 1):

        if A % i == 0 and isprime(i):

            answer.append(i)

for i in range(len(answer)):

    while A % answer[i] == 0:

        print(answer[i])

        A //= answer[i]

일단 이렇게 어렵게? 풀었다. 이제 소수 관련 개념은 어느정도 잡힌 듯 하다.

<라이브러리 sympy사용_런타임에러_코테에는 사용 불가>

import sys

input = sys.stdin.readline

from sympy import isprime

A = int(input())

answer = []

if A > 1:

    for i in range(2, A + 1):

        if A % i == 0 and isprime(i):

            answer.append(i)

for i in range(len(answer)):

    while A % answer[i] == 0:

        print(answer[i])

        A //= answer[i]

 

<다른 사람 코드 분석>

이 코드 신기하네.

1. i = 1일때 아무 동작 안하고, 2와 3일때 그냥 하나씩 출력하게 설계 => 5일때도

2. 이제 N은 4보다 크거나 같음 => 이걸 i * i로 표현해서 i = 2부터 시작

    ㄴ i * i 조건은 정수 N의 제곱근보다 작거나 같아야 한다? -> 이게 조금 이해가 안가네.

 

일단 기억하고 pass

N = int(input())

i = 2

while i * i <= N:

    while N % i == 0:

        print(i)

        N //= i

    i += 1

if N > 1:

    print(N)