[백준] 8단계: 기본 수학2

1. [1978] 소수 찾기

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

n = int(input())
num_list = list(map(int, input().split()))
prime_cnt = 0

for i in num_list:
    cnt = 0
    if i == 1: # 1은 소수가 아니기 때문에 건너띔
        continue
    for j in range(2, i+1):
        if i % j  == 0:
            cnt += 1
    if cnt == 1:
        prime_cnt += 1
print(prime_cnt)

Comment: for문으로 조건에 맞는 list 인자를 pop하겠다는 발상은 앞으로 폐기 처리할 것, 소수 수를 새는 것은 어떻게 가능했는데, 소수 배열을 내보내는 방법은 아직 고민 중.. 다음 문제가 아마 소수 배열을 만들어야 할 것 같다.

2. [2581] 소수

자연수 M과 N이 주어질 때 M이상 N이하의 자연수 중 소수인 것을 모두 골라 이들 소수의 합과 최솟값을 찾는 프로그램을 작성하시오. 예를 들어 M=60, N=100인 경우 60이상 100이하의 자연수 중 소수는 61, 67, 71, 73, 79, 83, 89, 97 총 8개가 있으므로, 이들 소수의 합은 620이고, 최솟값은 61이 된다.

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

prim_num = []
for i in range(M, N+1):
    error = 0
    if i > 1:
        for j in range(2, i):
            if i % j == 0:
                error += 1
                break
        if error == 0:
            prim_num.append(i)

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

3. [11653] 소인수분해

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

N = int(input())

for i in range(2, N+1):
    if N % i == 0:
        while N % i == 0:
            print(i)
            N = int(N / i)

4. [1929] 소수 구하기

M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.

M, N = map(int, input().split())

for i in range(M, N+1):
    error = 0
    if i > 1:
        for j in range(2, int(i**0.5) + 1):
            if i % j == 0:
                error += 1
                break
        if error == 0:
            print(i)

5. [4948] 베르트랑 공준

베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼프가 1850년에 증명했다. 예를 들어, 10보다 크고, 20보다 작거나 같은 소수는 4개가 있다. (11, 13, 17, 19) 또, 14보다 크고, 28보다 작거나 같은 소수는 3개가 있다. (17,19, 23) 자연수 n이 주어졌을 때, n보다 크고, 2n보다 작거나 같은 소수의 개수를 구하는 프로그램을 작성하시오. 

prim_num = [0]*2 + [1]*246912

for i in range(2, 246913):
    if prim_num[i]:
        error = 0
        for j in range(2, int(i**0.5) + 1):
            if i % j == 0:
                error += 1
                prim_num[i]= 0
                break

while True:
    M = int(input())
    
    if M == 0:
        break

    print(sum(prim_num[M+1:M*2+1]))

6. [9020] 골드바흐의 추측

1보다 큰 자연수 중에서  1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아니다. 골드바흐의 추측은 유명한 정수론의 미해결 문제로, 2보다 큰 모든 짝수는 두 소수의 합으로 나타낼 수 있다는 것이다. 이러한 수를 골드바흐 수라고 한다. 또, 짝수를 두 소수의 합으로 나타내는 표현을 그 수의 골드바흐 파티션이라고 한다. 예를 들면, 4 = 2 + 2, 6 = 3 + 3, 8 = 3 + 5, 10 = 5 + 5, 12 = 5 + 7, 14 = 3 + 11, 14 = 7 + 7이다. 10000보다 작거나 같은 모든 짝수 n에 대한 골드바흐 파티션은 존재한다.

2보다 큰 짝수 n이 주어졌을 때, n의 골드바흐 파티션을 출력하는 프로그램을 작성하시오. 만약 가능한 n의 골드바흐 파티션이 여러 가지인 경우에는 두 소수의 차이가 가장 작은 것을 출력한다.

def is_prime(n):
    if n == 1:
        return False
    for i in range(2, int(n**0.5) + 1):
        if n % i == 0:
            return False
    return True

for _ in range(int(input())):
    n = int(input())
    
    a, b = n // 2, n // 2
    while a > 0:
        if is_prime(a) and is_prime(b):
            print(a, b)
            break
        else:
            a -= 1
            b += 1

 

Comment: 시간 초과 해결하기가 어려웠습니다. 난이도 올라가는 게 느껴지는 단계였어요.