약수, 배수와 소수

약수들의 합 : 9506

문제

예제

나의 풀이

완전수일 때 출력하는 방법을 잘 모르겠어서 헤맸는데 이번 기회에 *과 sep()에 대한 기념을 다시 짚고 넘어 가야할 것 같다.

while True:
    n = int(input())
    if n == -1:
        break
    else:
        num_list =[]
        num = 0
        for i in range(1, n+1):
            if n % i == 0 and i != n:
                num += i
                num_list.append(i)
        if num == n:
            print(f'{n} = ', end='')
            print(*num_list,sep = ' + ')
        else:
            print(f'{n} is NOT perfect.')

다른 풀이

while True:
   n = int(input())
   if n == -1:
       break
   else:
       num_list =[]
       num = 0
       for i in range(1, n+1):
           if n % i == 0 and i != n:
               num += i
               num_list.append(i)
       if num == n:
           result = f'{n} = '
           result += ' + '.join(map(str, num_list))
           print(result)
       else:
           print(f'{n} is NOT perfect.')

위 코드에서 result가 출력되는 방식이 잘 이해 안돼서 출력 방식을 남겨 놓는다. 잊어버리지 말아야지.

result = f'{n} = '        # result = "6 = "
result += ' + '.join(map(str, num_list))  # result += "1 + 2 + 3"
print(result)  # 출력: "6 = 1 + 2 + 3"

소수 찾기 : 1978

문제

예제

나의 풀이

소수에서 1은 제외되므로 2부터 자기 자신까지의 숫자로 자기 자신을 나누었을 때 나누어 떨어지는 숫자를 찾고, 그 숫자가 자기 자신과 같은 숫자가 아니라면 1과 자기 자신 외의 약수를 가진 것을 의미하므로 아래와 같이 풀었다.

n = int(input())
numbers = list(map(int, input().split()))
count = 0

for num in numbers:
    for i in range(2, num+1):
        if num % i == 0:
            if num != i:
                break
            count+=1
print(count)

다른 풀이

소수 구하기에서 N의 값이 10,000 이상의 큰 값이라면 에라토스테네스의 체를 활용하는 것이 훨씬 효율적이다.

def sieve(limit):
    is_prime = [True] * (limit + 1)
    is_prime[0] = is_prime[1] = False  # 0과 1은 소수가 아님

    for i in range(2, int(limit**0.5) + 1):
        if is_prime[i]:
            for j in range(i * i, limit + 1, i):
                is_prime[j] = False  # 배수는 소수가 아님

    return is_prime  # 소수 여부 리스트 반환

# 입력 받기
n = int(input())  # 숫자의 개수
numbers = list(map(int, input().split()))  # 숫자 리스트

# 가장 큰 숫자까지의 소수 여부를 미리 계산
prime_check = sieve(max(numbers))

# 주어진 숫자 중 소수 개수 세기
print(sum(1 for num in numbers if prime_check[num]))