9. [9단계] 제목: 약수, 배수와 소수 단계

1단계.
4 × 3 = 12이다.
이 식을 통해 다음과 같은 사실을 알 수 있다.
3은 12의 약수이고, 12는 3의 배수이다.
4도 12의 약수이고, 12는 4의 배수이다.
두 수가 주어졌을 때, 다음 3가지 중 어떤 관계인지 구하는 프로그램을 작성하시오.
1. 첫 번째 숫자가 두 번째 숫자의 약수이다.
2. 첫 번째 숫자가 두 번째 숫자의 배수이다.
3. 첫 번째 숫자가 두 번째 숫자의 약수와 배수 모두 아니다.
입력은 여러 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 10,000이 넘지 않는 두 자연수로 이루어져 있다.

마지막 줄에는 0이 2개 주어진다. 두 수가 같은 경우는 없다.

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

답: while (1):
    n1,n2=map(int,input().split())

    if n1==0 and n2==0:
        break
    elif n2%n1==0:#약수인 경우
        print('factor')
    elif n1%n2==0: #배수인 경우
        print('multiple')
    else:#둘 다 아닌 경우
        print('neither')

첫 번째 수와 두 번째 수를 이용해서 약수와 배수를 구하는 문제다. n1과 n2가 0이면 반복문은 끝난다. 예를 들어 n1이 4이고, n2가 8이라면? 8을 4로 나누면 2가 튀어나오고 4가 8의 약수임을 알 수 있다. 반대의 경우라면 배수일 것.

둘 다 아니면 neithet를 반환한다.

---

2단계.
어떤 자연수 p와 q가 있을 때, 만일 p를 q로 나누었을 때 나머지가 0이면 q는 p의 약수이다.
6의 약수는 1, 2, 3, 6, 총 네 개다.
두 개의 자연수 N과 K가 주어졌을 때, N의 약수들 중 K번째로 작은 수를 출력하는 프로그램을 작성하시오.

답: N, K = map(int, input().split())
lst = []
for i in range(1,N+1) :
    if N % i == 0 :
        lst.append(i)

if len(lst) < K : # 약수의 개수가 K보다 작을 때
    print(0)
else :
    print(lst[K-1]) # 인덱스 번호에 맞춰서 K-1번째로 해야 함

먼저 N과 K를 입력받는다. 이후 lst라는 배열을 선언한다. 이제 for문은 1부터 N까지 돌아갈 것이다. 만일 N를 0부터 N까지 나눈 나머지가 0이면 배열에 i값을 추가한다. (약수이니깐)

길이가 K보다 작으면 그냥 0, 아니면 인덱스에 맞추어 lst[K-1]을 출력해야 한다.

---

3단계.
어떤 숫자 n이 자신을 제외한 모든 약수들의 합과 같으면, 그 수를 완전수라고 한다.
예를 들어 6은 6 = 1 + 2 + 3으로 완전수이다.
n이 완전수인지 아닌지 판단해 주는 프로그램을 작성하라.

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

n이 완전수라면, n을 n이 아닌 약수들의 합으로 나타내어 출력한다.
이때, 약수들은 오름차순으로 나열해야 한다.
n이 완전수가 아니라면 n is NOT perfect. 를 출력한다.

답: while (1):
    n = int(input())
    if n == -1:
        break
    arr = []
    for i in range(1, n):
        if (n % i == 0):
            arr.append(i)
    if (sum(arr) == n):
        print(n, "=", end=" ")
        print(*arr, sep=" + ")
    else:
        print(n, "is NOT perfect.")

약수를 구하고, 그 약수를 다 더한 값이 n이면 완전수이다. 2단계 문제에서 살짝 더 응용된 문제다. 코드는 2단계와 비슷하나, sum함수를 이용해서 모든 약수를 다 더하는 코드가 추가되었다. 모든 약수를 다 더할 때 n과 같으면 arr의 배열을 한 줄 출력해 주고 공백에 +을 넣어준다. 그게 아니면 is NOT perfect를 출력한다.

---

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

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

답: n = int(input())
nums = list(map(int, input().split()))
count = 0

for x in nums: 
  for i in range(2, x+1):
    if (x % i == 0):
      if (x == i):
        count += 1
      break 

print(count)

소수란 자기 자신과 1로만 나뉘는 수이다. 예시로는 2와 3... 5... 7.. 이렇게 있다.

먼저 n개를 입력받는다. (그리고 더 이상 안 쓴다) 이후 n개의 수를 입력받는다 - nums (list로 받는다)

소수의 개수를 0으로 초기화한다. 이후 0부터 nums에 포함되는 수만큼 for문이 돌아간다. 소수는 2부터 시작이어서 2부터 x까지 돌아가야 한다. x만큼 2부터 x를 나눌 때 나머지가 0이라면? 그리고 그게 동일하다면? 소수이라고 생각할 수 있다.

예를 들어 3이라고 생각하자. 3은 1부터 3까지 나눌 수 있는데, 1과 3은 3으로 나눌 때 나머지가 0이다.

이후 count에 1을 더한다. x가 다 돌아가면 break 되고 빠져나간다.

---

5단계.
자연수 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이하의 자연수 중 소수가 없을 경우는 첫째 줄에 -1을 출력한다.

답: import math

# 소수 판별 함수
def is_prime(num):
    if (num < 2):
        return False
    for i in range(2, int(math.sqrt(num)) + 1):
        if (num % i == 0):
            return False
    return True

# 입력 처리
M = int(input())
N = int(input())

# 소수 리스트 작성
prime_numbers = []
for i in range(M, N + 1):
    if is_prime(i):
        prime_numbers.append(i)

# 결과 출력
if prime_numbers:
    print(sum(prime_numbers))
    print(min(prime_numbers))
else:
    print(-1)

챗 GPT의 힘을 빌렸다. import를 이용, math 라이브러리 함수를 가져온다. 

def is_prime(num): 은 num가 소수인지 아닌지 판별하는 함수다. 이후 M과 N를 입력받는다. 그다음 소수 리스트를 작성한다. M부터 N까지 만일 이 안에 소수가 있다면 리스트에 추가해 준다.

그러면 prime_numbers에 모든 소수가 들어간다. 만일 소수가 존재하면 sum함수로 총합을 출력, min함수로 최솟값을 출력한다. 그게 아니라면 -1을 반환한다.

---

6단계.
정수 N이 주어졌을 때, 소인수분해하는 프로그램을 작성하시오.
N의 소인수분해 결과를 한 줄에 하나씩 오름차순으로 출력한다. N이 1인 경우 아무것도 출력하지 않는다.

답: n = int(input())

if (n == 1):
    print("")

# 2부터 하나씩 나눠보기
for i in range(2, n+1):
    if (n % i == 0):
     #해당 숫자로 나눌 수 없을 때까지 나누기
        while (n % i == 0):
            print(i)
            n = n / i

소인수분해란 소수인 인수로 나누는 것이다. 어쩔 수 없다. 2부터 입력받은 n까지 계속 계속 나눈다.

반복문은 n을 n까지 나눈다. 못 나누게 되면 반복문은 끝나게 된다.

결론

챗 gpt가 푼 풀이는 파이썬의 내부 수학 함수를 가져오는 식으로 풀었다.

다른 구글링에서는 보기 힘든 코드였다. 생각보다 챗 gpt는 강하다.