[기본수학 2] 소인수분해, 소수 구하기

11653번: 소인수분해

 

1929번: 소수 구하기

 

소인수 분해 문제는 굳이 소수를 구하는 방식으로 풀어야 하나? 하는 생각이 들어서 그냥 쉽게 작성했다.

 

import sys
from sys import stdin

test = int(stdin.readline())


def get_factorization(no: int):
    for i in range(2, no):
        if no % i == 0:
            print(i)
            return get_factorization(no // i)

    if no != 1:
        print(no)


get_factorization(test)

그냥 안 나누어 떨어질 때까지 나눈다. 끝

 

 

소수구하기 문제 역시 기존에 사용했던 소수 로직 재사용 느낌이 강해서 그냥 풀었다.

from sys import stdin
import math

test = list(map(int, stdin.readline().split(" ")))

# 10 이하 소수 리스트
pn_list = [2, 3, 5, 7]

# 나머지 목록
rest_list = [1, 3, 7, 9]


def check_prime_no(no: int):
    if no == 1:
        return False

    # 이미 소수 리스트에 속한 요소면 소수
    if no in pn_list:
        return True
    
    rest = no % 10
    if rest not in rest_list:
        return False

    for j in range(2, math.ceil(math.sqrt(no)) + 1):
        if no % j == 0:
            return False

    return True


for i in range(test[0], test[1] + 1):
    if check_prime_no(i):
        print(i)

 

보다보니 소수 구하는 로직이 되게 조잡한 느낌이다;; 무작정 재사용할건 아닌 것 같다...