[BOJ] 2581번 - 소수찾기

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

<출력>
M이상 N이하의 자연수 중 소수인 것을 모두 찾아 첫째 줄에 그 합을, 둘째 줄에 그 중 최솟값을 출력한다. 
단, M이상 N이하의 자연수 중 소수가 없을 경우는 첫째 줄에 -1을 출력한다.


<예제>
60				620
100				61

import math

N = int(input())
M = int(input())
prime_list = []

# 1. i가 나눠떨어진다면 제외
# 2. 나눠 떨어지지 않는다면 m += 1
# 3. 그래도 안되면 prime_list에 추가
# 4. list에 하나도 추가되지 않았다면 -1 반환

for i in range(N, M + 1):           
    i_sqrt = int(math.sqrt(i))
    if i > 1:
        for m in range(2, i_sqrt + 1):            
            if i % m == 0:              
                break
            else:
                continue
        else:
            prime_list.append(i)            


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

에라토스테네스의 체

• 위 문제에서는 소수인지 아닌지 판별하여 문제를 해결하였지만 시간이 오래 걸림
• 2의 배수, 3의 배수 이런 식으로 소수의 배수들을 지워나가며 소수를 찾아내는 방식인 에라토스테네세의 체를 이용해서 소수 찾기 프로그램 진행

def prime_list(n):
    # 에라토스테네스의 체 초기화: n개 요소에 True 설정(소수로 간주)
    sieve = [True] * n

    # n의 최대 약수가 sqrt(n) 이하이므로 i=sqrt(n)까지 검사
    m = int(n ** 0.5)				   # 4
    for i in range(2, m + 1):		   # 2, 3, 4
        if sieve[i] == True:           # 2가 소수인 경우
            for j in range(i+i, n, i): # i이후 i의 배수들을 False 판정 (4부터 20까지 2씩 더해가면서) 
                sieve[j] = False

    # 소수 목록 산출
    return [i for i in range(2, n) if sieve[i] == True]
    
    
# prime_list(20)
# [2, 3, 5, 7, 11, 13, 17, 19]

# max(prime_list(1000000))
# 999983

위키백과 - 에라토스테네스의 체

[BOJ] 4948번 - 베르트랑 공준

베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다.
자연수 n이 주어졌을 때, n보다 크고, 2n보다 작거나 같은 소수의 개수를 구하는 프로그램을 작성하시오. 

<입력>
입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 케이스는 n을 포함하는 한 줄로 이루어져 있다.

입력의 마지막에는 0이 주어진다.

<출력>
각 테스트 케이스에 대해서, n보다 크고, 2n보다 작거나 같은 소수의 개수를 출력한다.

<예제>
1						1
10						4
13						3
100						21
1000					135
10000					1033
100000					8392
0

위 처럼 풀었더니 시간초과

import math

while True:
    N = int(input())
    cnt = 0

    if N == 0:
        break

    for i in range(N + 1, (2*N + 1)):
        i_sqrt = int(math.sqrt(i))
        if i > 1:
            for m in range(2, i_sqrt + 1):
                if i % m == 0:
                    break
                else:
                    continue
            else:
                cnt += 1
    print(cnt)

에리스토테네스의 체를 이용하여 해결

while True:
    N = int(input())  
    
    if N == 0:				# 0에 대한 처리도 적절한 곳에 해주어야 함
        break

    prime_list = [True for _ in range(N * 2 + 1)]
    prime_list[0], prime_list[1] = False, False			# 0,1
    cnt = 0

    m = int((2 * N) ** 0.5)  
    for i in range(2, m + 1):  
        if prime_list[i]:
            for j in range(i + i, N * 2 + 1, i):  
                prime_list[j] = False			# 체를 이용하여 판별해놓고

    for i in range(N + 1, (2 * N + 1)):  
        if prime_list[i]:
            cnt += 1
    print(cnt)