self.winter.(05). 소수판별과 에라토스테네스의 체 (시간초과의 저주)

🧐 백준 2581 (소수의 원리 이용)

🤫 해결의 실마리 

🤔 소수의 원리 
소수의 원리 => 약수의 개수가 2개 (1과 자기자신)

🤔 Algorithm 과정 
1. num이라는 빈 리스트에 입력된 M ~ N까지의 숫자를 넣는다.
2. 약수의 개수를 세는 cnt라는 변수를 선언, 0으로 초기화한다.
3. 소수를 담을 리스트 dec을 선언한다.
4. num리스트의 원소를 차례로 돌면서 i % j == 0 즉, 약수일 때, cnt값을 증가시킨다.
5. 이렇게 약수의 개수가 담긴 cnt변수에 대해 만약 약수의 개수가 2개라면(cnt == 2) 소수인것!
따라서 소수라면 dec 리스트에 원소를 추가해주고 cnt==0이라면 소수가 없는 것이므로 0을 출력!

🤫  solution_2581

 

M, N = int(input()), int(input())
num = []
for i in range(N-M+1):
    num.append(i+M)

dec = []
for i in num:
    cnt = 0
    for j in range(1, i+1):
        if i % j == 0:
            cnt += 1
    if cnt == 2:
        dec.append(i)
if len(dec) == 0:
    print(-1)
else:
    print(sum(dec))
    print(min(dec))

 

🧐 백준 1929 (에라토스테네스의 체) _ 앞으로 계속 이 문제에서 파생하여 문항을 해결함

🤫 해결의 실마리 

🤔 에라토스테네스의 체 (Sieve of Eratosthenes)

 

에라토스테네스의 체 원리는 다음과 같다.
1. 소수가 아닌 1을 지운다.
2. 2의 배수를 지운다.
3. 앞서 지운 2의 배수가 아닌 것들 중 최소값인 3의 배수를 지운다.
4. 앞서 지운 2, 3의 배수가 아닌 값들 중 최소값인 5의 배수를 지운다.
5. 이 과정을 반복하여 걸러지는 것들이 비로소 소수가 된다.

https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

이러한 에라토스테네스의 체는 "특정 구간이 주어졌을 때" 매우 빠르게 소수를 도출할 수 있다.
위의 2581번처럼 풀면 시간복잡도는 O(n)으로 비교적 시간이 오래 걸린다.
하지만 에라토스테네스의 체의 시간복잡도는 O(nlog(log n))으로 매우 빠르게 도출이 가능하다.
또한 약수의 경우, 2*4, 4*2 처럼 반복이 되기 때문에
가장 중요한 것은 범위의 마지막 수의 루트 값까지만 반복함으로 시간을 더욱 줄일 수 있다!


🤔 Algorithm 과정 
알고리즘과정은 위에서 설명하는 에라토스테네스의 방식을 차용하였다.
또한 코드에 대한 설명은 아래 그림으로 대체하겠다.

🤫  solution_1929

m, n = map(int, input().split())
num = [i for i in range(max(2, m), n+1)]  # m ~ n사이 숫자를 넣은 리스트 (단, 1은 제외)
dec_sqr_n = []   # n의 제곱근까지의 범위안에서 소수를 집어 넣을 리스트

for i in range(2, int(n**0.5) + 1):   # 2에서 n의 제곱근까지만 반복
    if i in num:
        dec_sqr_n.append(i)
    num = [j for j in num if j % i != 0]

print(*(dec_sqr_n + num), sep = "\n")

 

 

 

🧐 백준 4948 (에라토스테네스의 체)

🤫 해결의 실마리 

🤔 에라토스테네스의 체 (Sieve of Eratosthenes)

🤔 Algorithm 과정 
위 1929와 거의 동일한 방식으로 풀었지만 방법은 다음과 같다.
1. n의 범위 사이의 자연수를 저장하는 num 리스트를 생성한다. (1 ≤ n ≤ 123456)
2. 리스트 num을 1929번 풀이처럼 소수만 존재하도록 만들어준다.
3. 1929와 같은 방식으로 n의 범위사이에 존재하는 모든 소수가 담긴 decimal이라는 리스트를 생성해준다.
4. 0이 들어오기 전까지 while문을 이용해 입력을 받아주고
5. decimal 리스트에서 입력의 범위에 해당하는 값들의 개수를 세어 출력해준다.

 

🤫  solution_4948 (시간초과)

def decimal(N):
    n = N+1
    num = [i for i in range(n, 2*N + 1)]
    dec_half = []
    for i in range(2, int((2*N)**0.5) + 1):
        if i in num:
            dec_half.append(i)
        num = [j for j in num if j % i != 0]
    return len(dec_half+num)

num = -1
while True:
    num = int(input())
    if num == 0:
        break
    else:
        print(decimal(num))

 

처음 짠 코드로 1929와 비슷하게 함수를 생성하여 풀었으나 시간초과가 발생하였다.
시간복잡도를 염두하지 않고 머리를 장식으로 두고 문제에 접근한 결과라 생각할 수 밖에 없다.
함수에서 2중 for문을 사용한 것을 while문에서 계속 받으니 그럴 수 밖에...

🤫  solution_4948

from math import sqrt

# 1 <= n <= 123456 사이 자연수를 담은 리스트 생성
num = [i for i in range(2, 123456 * 2)]

# 리스트 num을 이전처럼 소수만 있게 만들어주기.
dec_half = []
for i in range(2, int(sqrt(123456*2)) + 1):
    if i in num:
        dec_half.append(i)
    num = [j for j in num if j%i != 0]

decimal = dec_half + num

n = -1
while True:
    n = int(input())
    if n == 0:
        break
    # decimal 리스트에서 입력의 범위에 해당하는 값들의 개수를 세어 출력
    print(len([i for i in decimal if n < i <= 2*n]))

 

🧐 백준 9020 (에라토스테네스의 체)

🤫 해결의 실마리 

🤔 에라토스테네스의 체 (Sieve of Eratosthenes)

🤔 Algorithm 과정 
두 소수의 차이가 가장 작은 것의 의미를 생각해보면 다음과 같다.
소수간의 차이가 작을수록 최대값의 절반과 가까워진다! 
16으 예로 들자면 다음과 같다.
[3, 13], [5, 11]  =>  3  5  (8)  11  13

따라서 핵심은 시간초과가 걸리지 않으려면 소수의 절반만 훑어야 한다.

 

🤫  solution_9020 (시간초과)

T = int(input())
n = [int(input()) for _ in range(T)]

num = [i for i in range(2, 10001)]
dec_half = []
for i in range(2, 100 + 1):
    if i in num:
        dec_half.append(i)
    num = [j for j in num if j % i != 0]
decimal = dec_half + num

for i in n:
    dec = []
    for j in range(len(decimal)):
        for k in range(j, len(decimal)):
            if i == decimal[j] + decimal[k]:
                dec.append([decimal[j], decimal[k]])
    print(*dec[-1])

처음 짠 코드로 문제점은 소수의 전체를 계속 훑으면서 비교를 진행하기 때문에 위의 알고리즘보다 2배 이상의 시간이 걸릴 가능성이 높다.
먼저 위의 코드를 짠 과정은 다음과 같다.
1. 먼저 범위에 해당하는 모든 소수를 담는 리스트를 생성하고 
2. 그 리스트 안에서 두 소수간의 덧셈이 입력값과 동일한 것을 찾아서 dec이라는 리스트에 넣는다.
3. dec에는 [[3, 5]], [[3, 7], [5, 5]], [[3, 13], [5, 11]] 처럼 들어간 것이므로 
4. 각 리스트의 마지막 인덱스에 해당하는 리스트가 차이가 가장 작은 소수 리스트인것.
이를 for문을 이용해 출력하였다.

🤫  solution_9020

num = [i for i in range(2, 10000 + 1)]
dec_half = []
for i in range(2, 100 + 1):
    if i in num:
        dec_half.append(i)
    num = [j for j in num if j%i != 0]
decimal = dec_half + num

T = int(input())
for i in range(T):
    n = int(input())
    n_half = n // 2
    for j in range(n_half, 1, -1):
        if j in decimal and n - j in decimal:
            print(j, n - j)
            break