단계별: 약수,배수와 소수 (5086, 2501, 9506, 1978, 2581, 11653) (python3)

예에전에 푼 문제 정리

 

배수와 약수 - 5086

while True:
    a, b = map(int, input().split())
    if a == 0 and b == 0:
        break
    elif b%a == 0:
        print("factor")
    elif a%b == 0:
        print("multiple")
    elif a%b != 0 or b%a != 0:
        print("neither")

 

약수 구하기 - 2501

N의 약수를 구하고 리스트를 만들어서 오름차순으로 정렬 후 K번째 수를 출력하면됨. 약수가 없으면 0출력

import sys

n, k = map(int, sys.stdin.readline().rstrip().split())
li = []

for i in range(1, int(n**(1/2))+1):
    if n%i == 0:
        li.append(i)
        if i**2!=n:
            li.append(n//i)
    
li.sort()

if len(li) < k:
    print(0)
else:
    print(li[k-1])

제곱근까지만 계산을 해서 시간복잡도를 줄임

시간 복잡도 : O(N^(1/2))

 

약수들의 합 - 9506

for문 안에 리스트 l을 넣어서 초기화시켜줘야함

a = []

while True:
    n = int(input())
    if n == -1:
        break
    a.append(n)


for n in a:
    l = []
    for i in range(1, n):
        if n%i == 0:
            l.append(i) 

    if sum(l) == n:
        print(n , "=" , " + ".join(str(i) for i in l))
    else:
        print(n , "is NOT perfect.")

 

소수 찾기 - 1978

n = int(input())
sec_n = list(map(int, input().split()))

count = 0
for n in sec_n:
    if n != 1:
        for i in range(2, n):
            if n % i == 0:
                break
        else:
            count+=1

print(count)

 

소수 - 2581

m = int(input())
n = int(input())
prime = [ ]

for i in range(m, n+1): #m부터 n까지
    if i > 1: #1보다 큰 수
        for j in range(2, i):
            if (i % j) == 0:
                break
        else:
            prime.append(i)

if len(prime) > 0:
    print(sum(prime))
    print(min(prime))
else:
    print(-1)

 

소인수분해 - 11653

import math

n = int(input())
i = 2

while i <= math.sqrt(n):
    if n % i != 0:
        i += 1
    else:
        print(i)
        n //= i

if n > 1:
    print(n)