9. 약수, 배수와 소수

https://www.acmicpc.net/step/10

약수, 배수와 소수 단계

6문제

---

백준 / 5086번

문제

4 × 3 = 12이다.

이 식을 통해 다음과 같은 사실을 알 수 있다.

3은 12의 약수이고, 12는 3의 배수이다.

4도 12의 약수이고, 12는 4의 배수이다.

두 수가 주어졌을 때, 다음 3가지 중 어떤 관계인지 구하는 프로그램을 작성하시오.

1. 첫 번째 숫자가 두 번째 숫자의 약수이다.
2. 첫 번째 숫자가 두 번째 숫자의 배수이다.
3. 첫 번째 숫자가 두 번째 숫자의 약수와 배수 모두 아니다.

 

입력

입력은 여러 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 10,000이 넘지않는 두 자연수로 이루어져 있다. 마지막 줄에는 0이 2개 주어진다. 두 수가 같은 경우는 없다.

 

출력

각 테스트 케이스마다 첫 번째 숫자가 두 번째 숫자의 약수라면 factor를, 배수라면 multiple을, 둘 다 아니라면 neither를 출력한다.

 

풀이

-Python3

while True :
    A,B= map(int, input().split())
    #마지막 0 0이 들어오면 끝내기
    if A==B==0 :
        break

    if A > B:
        if A%B ==0:
            print("multiple")
            continue
    elif A < B :
        if B%A ==0:
            print("factor")
            continue
    #둘다 아닌 경우
    print("neither")

0 0이 입력으로 들어오면 끝내는 코드이므로 while True로 계속 입력을 받도록 하고, 반복문 초반에서 if문으로 탈출할 수 있게 둔다.

 

A가 B보다 클 때 A/B의 나머지가 없다면 A가 B의 배수라고 볼 수 있다.

A가 B보다 작을 때 B/A의 나머지가 없다면 반대로 A가 B의 약수라고 볼 수 있다.

따라서 두 경의 if문을 두고 continue로 새 반복문을 시작하게 한다. (break로 끊으면 반복문 활성화가 안 돼서 오류남)

---

백준 / 2501번

문제

어떤 자연수 p와 q가 있을 때, 만일 p를 q로 나누었을 때 나머지가 0이면 q는 p의 약수이다. 

• 6 ÷ 1 = 6 … 0
• 6 ÷ 2 = 3 … 0
• 6 ÷ 3 = 2 … 0
• 6 ÷ 4 = 1 … 2
• 6 ÷ 5 = 1 … 1
• 6 ÷ 6 = 1 … 0

그래서 6의 약수는 1, 2, 3, 6, 총 네 개이다.

입력

첫째 줄에 N과 K가 빈칸을 사이에 두고 주어진다. N은 1 이상 10,000 이하이다. K는 1 이상 N 이하이다.

 

출력

첫째 줄에 N의 약수들 중 K번째로 작은 수를 출력한다. 만일 N의 약수의 개수가 K개보다 적어서 K번째 약수가 존재하지 않을 경우에는 0을 출력하시오.

 

풀이

-Python3

N, K= map(int, input().split())
factor = [] #약수를 저장하는 리스트

#약수를 구해서 리스트에 넣기
for i in range(1, N+1, 1) :
    if N % i == 0 :
        factor.append(i)

#약수의 수가 K보다 작다면 0출력
if len(factor) < K :
    print(0)
#그렇지 않을 경우 K번째 약수 출
else :
    print(factor[K-1])

약수들의 리스트를 정의해두고 N의 약수 리스트를 저장해두었다가 K번째 약수를 호출하면 된다.

나름 간단...

배열의 원수 개수를 구할 때 len(배열)을 쓰는 점을 헷갈렸고, 인덱스는 0부터 시작하기 때문에 K-1번째 인덱스를 찾아야 한다는 점을 헷갈렸다.

---

백준 / 9506번

문제

어떤 숫자 n이 자신을 제외한 모든 약수들의 합과 같으면, 그 수를 완전수라고 한다.

예를 들어 6은 6 = 1 + 2 + 3 으로 완전수이다.

n이 완전수인지 아닌지 판단해주는 프로그램을 작성하라.

입력

입력은 테스트 케이스마다 한 줄 간격으로 n이 주어진다. (2 < n < 100,000)

입력의 마지막엔 -1이 주어진다.

 

출력

테스트케이스 마다 한줄에 하나씩 출력해야 한다.

n이 완전수라면, n을 n이 아닌 약수들의 합으로 나타내어 출력한다(예제 출력 참고).

이때, 약수들은 오름차순으로 나열해야 한다.

n이 완전수가 아니라면 n is NOT perfect. 를 출력한다.

 

풀이

-Python3

while True :
    #리스트 초기화 및 입력 받기
    factor = []
    n = int(input())
    #-1이 들어오면 멈추기
    if n == -1 :
        break

    #약수가 n을 포함하지 않도록 약수 리스트를 만든다.
    for i in range(1, n, 1) :
        if n % i == 0 :
            factor.append(i)

    #완전수 판별
    if sum(factor) == n :
        print(n, "=", " + ".join(map(str, factor)))
    else :
        print(n, "is NOT perfect.")

약수 리스트를 만들고 sum(factor)로 약수의 합이 n과 같은지 판별을 해주면 된다.

그건 별로 어렵지 않았는데 약수 리스트를 꺼내와서 출력하는 게 헷갈렸다.

print(n, "=", " + ".join(map(str, factor)))

• map(str, factor) : factor의 요소들을 string 형태로 문자열의 합치는 수식이다.
• " + ".join(리스트) : 각 원소들을 " + " 문자로 결합하여 출력 문자열을 생성하는 수식이다.

---

백준 / 1978번

문제

주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오.

 

입력

첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다.

 

출력

주어진 수들 중 소수의 개수를 출력한다.

 

풀이

-Python3

N = int(input())
#파이썬에서는 입력을 리스트로 한번에 넣을 수도 있음
numbers = map(int, input().split())
count = 0

#리스트의 개수 N만큼 소수 판별을 반복한다.
for number in numbers :
    #입력이 1일 경우 나눗셈 오류를 방지하기 위해 예외 처리
    if number == 1 :
        continue
    #소수 판별
    is_prime = True
    for j in range(2, number, 1) :
        if number % j == 0 :
            is_prime = False
            continue
    if is_prime:
        count += 1

#소수개의 개수 출력
print(count)

원래 소수 판별용 변수를 따로 안 뒀었는데 계산이 제대로 안 돼서 추가한 후기...

소수를 판별하는 반복문에서 continue가 되면 맨 처음 for number in numbers 시작으로 가는 게 아니라 소수를 판별하는 반복문을 재시작하게 된다. 그래서 입력이 1이 아닌 모든 경우에 count+=1이 실행되었다. 여기서 is_prime을 기본 True로 두고, 소수가 아닌 if문에 걸리면 false로 바꾼다. 이후 반복계산문이 종료되고 is_prime 값에 따라서 count를 더하는 방식으로 수정해주었다.

 

*list로 입력을 한번에 넣을 수 있는 것...

*for i in 배열 으로 배열의 원소를 순차적으로 호출할 수 있는 것...

---

백준 / 2581번

문제

자연수 M과 N이 주어질 때 M이상 N이하의 자연수 중 소수인 것을 모두 골라 이들 소수의 합과 최솟값을 찾는 프로그램을 작성하시오.

예를 들어 M=60, N=100인 경우 60이상 100이하의 자연수 중 소수는 61, 67, 71, 73, 79, 83, 89, 97 총 8개가 있으므로, 이들 소수의 합은 620이고, 최솟값은 61이 된다.

 

입력

입력의 첫째 줄에 M이, 둘째 줄에 N이 주어진다.

M과 N은 10,000이하의 자연수이며, M은 N보다 작거나 같다.

 

출력

M이상 N이하의 자연수 중 소수인 것을 모두 찾아 첫째 줄에 그 합을, 둘째 줄에 그 중 최솟값을 출력한다. 

단, M이상 N이하의 자연수 중 소수가 없을 경우는 첫째 줄에 -1을 출력한다.

 

풀이

-Python3

M = int(input())
N = int(input())

#소수를 추가할 배열 primes
primes = []

#M이상 N이하의 자연수의 소수 판별 반복
for number in range(M, N+1) :
    #입력이 1일 경우 나눗셈 오류를 방지하기 위해 예외 처리
    if number == 1 :
        continue
    
    is_prime = True
    for j in range(2, number, 1) :
        if number % j == 0 :
            is_prime = False
            break
        
    if is_prime :
        primes.append(number)

#소수의 합 / 소수의 최솟값 출력
if len(primes) == 0 :
    print(-1)
else :
    print(sum(primes))
    print(min(primes))

앞 문제에서 조금만 손보면 된다.

M과 N사이를 반복문으로 돌면서 소수를 만족하는 수만 primes 리스트에 추가한다.

소수가 없을시에는 -1을 출력하고, 있다면 리스트의 합과 최솟값을 출력하면 된다.

---

백준 / 11653번 (⭐)

문제

정수 N이 주어졌을 때, 소인수분해하는 프로그램을 작성하시오.

 

입력

첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다.

 

출력

N의 소인수분해 결과를 한 줄에 하나씩 오름차순으로 출력한다. N이 1인 경우 아무것도 출력하지 않는다.

 

풀이

-Python3

import sys

N = int(input())

#N이 1일 경우 아무것도 출력하지 않음
if N == 1 :
    sys.exit()

#소인수분해
for i in range(2, N+1) :
    while N % i == 0 :
        N = N // i
        print(i)
    if N == 1 :
        break

오히려 반복문 때문에 이게 제일 헷갈린듯한.. ?

while N % 1 == 0 -> N이 i로 나누어 떨어질 때까지만 반복하라는 뜻