[Baekjoon] 약수와 소수와 배수

단계별 풀이 중 9단계인 약수, 소수, 배수에 대한 알고리즘 풀이 과정에서 느낀 점 및 내 풀이 결과를 나타내었다.

 

해당문제: https://www.acmicpc.net/step/10

---

🌈 파이썬 코드

📦 5086 1번 문제

문제 풀기 전 내 생각

일단 입력부분에서 0 0이 오면 반복문을 종료하는 구문을 짜야겠고만. break와 같은 탈출문구? 를 넣으면 될 듯 factor인지 multiple인지 neither인지를 출력하는 함수를 만드는 게 목표

def solution():
    # 연산의 횟수가 정확히 정해지지 않았으므로 while
    while True:
        a, b = map(int, input().split())
        # 탈출 구문
        if a + b == 0:
            break
        # 둘 중에 큰 수, 작은 수를 먼저 구해야한다.
        maxValue = max(a, b)
        minValue = min(a, b)
        # 이후 큰수로 작은 수를 나머지연산을 했을 때 나머지가 없다면 둘은 neither관계가 아니다.
        if not (maxValue % minValue == 0):
            print('neither')
            continue;
        print('factor' if maxValue == b else 'multiple')
solution()

 

📦 2501 2번 문제

# 약수 구하기 브론즈 3

def solution():
    a, b = map(int, input().split())
    list1 = [1, ]
    for i in range(2, a + 1):
        if a % i == 0:
            list1.append(i)
    return list1[b - 1] if len(list1) >= b else 0
print(solution())

• 약수 구하는 문제에서 소수와 헷갈려서 수학용어에 대해서 좀 구분을 잘 해야할 것 같다.

 

 

📦 9506 3번 문제

풀기 전 내 생각

완전수 = 자신을 제외한 모든 약수들의 합 == 자신 

완전수인지 아닌지 구하여라
완전수가 아니라면 "n is NOT perfect." 출력 완전수라면 약수들의 합으로 나타내어 출력(6 = 1 + 2 + 3)

# 약수들의 합 브론즈 1

def solution():
    while True:    
        N = input()
        if N == '-1':
            break
        result = f'{N} = 1'
        약수들 = [1, ]
        for i in range(2, int(N)):
            if int(N) % i == 0:
                약수들.append(i)
                result += f' + {str(i)}'
        print(f"{N} is NOT perfect." if sum(약수들) != int(N) else result)    
solution()

# 문자열을 추가하는 방식을 좀 더 쉽게 나타낼 순 없을까? >>개선 후
def solution():
    while True:    
        N = int(input())
        if N == -1:
            break
        result = f'{N} = 1'
        약수들 = [1, ]
        for i in range(2, N):
            if N % i == 0:
                약수들.append(i)
        print(f"{N} is NOT perfect." if sum(약수들) != N else f"{N} = " + " + ".join(map(str, 약수들)))    
solution()
# 문자열을 추가하는 방식을 좀 더 가독성 있게 나타내었다.

• 문자열 추가하는 방식에 대해서 나중에도 참고하며 사용할 수 있을 듯하다.

 

📦 9506 4번 문제

# 소수 찾기

import math
def solution():
    N = int(input())
    values = list(map(int, input().split()))
    count = N
    for value in values:
        if value == 1:
            count -= 1
            continue
        for i in range(2, int(math.sqrt(value)) + 1):
            if value % i == 0:
                count -= 1
                break
    return count
print(solution())

# 또 다른 풀이
def is_prime(num):
    if num <= 1:
        return False
    i = 2
    while i ** 2 <= num:
        if num % i == 0:
            return False
        i += 1
    return True

• 제곱근 표현 방식이 **0.5도 있는데 이것도 나름 괜찮은 것 같다
• 끝 범위를 제곱근으로 표현할수도 있지만 i의 값을 제곱으로 해서 계산해도 된다

 

📦 2581 5번 문제

# 소수 브론즈 2
import sys

def is_prime(num):
    if num <= 1:
        return False
    i = 2
    while i ** 2 <= num:
        if num % i == 0:
            return False
        i += 1
    return True

def solution():
    lines = sys.stdin.readline().rstrip()
    N = int(input())
    M = int(input())
    array1 = [i for i in range(N, M + 1) if is_prime(i)]
    if len(array1) > 0:
        print(sum(array1))
        print(array1[0])
    else: print(-1)
solution()

 

📦 11653 6번 문제

# 소인수분해 브론즈 1

# 개선 전
def solution():
    N = int(input())
    i = 2
    while N > 1:
        if N % i == 0:
            N = ( N // i)
            print(i)
            i = 2
        else:
            i += 1        
solution(

# 개선 후
def solution():
    N = int(input())
    i = 2
    while i ** 2 <= N:
        if N % i == 0:
            N //= i
            print(i)
            i = 2
            continue
        i += 1
    if N > 1:
        print(N)        
solution()

• 개선 전의 풀이는 시간이 상당히 소요되는 반면 개선 후에는 연산의 횟수를 많이 줄여서 시간이 많이 줄었다(600ms => 40ms)