[파이썬/python] 백준 4948번 : 베르트랑 공준 (🥈2) (에라토스테네스의 체)

https://www.acmicpc.net/problem/4948

import sys
input = sys.stdin.readline

while True:
    n = int(input())
    if n == 0 :
        break
    num=set(range(2,(n*2)+1))
    sub=set(range(2,n+1))
    
    for i in range(2,(n*2)+1):
        if i in num:
            num-=set(range(2*i,(n*2)+1,i))
    num-=sub
    print(len(num))

맞긴 했는데 시간이 3894ms였다

이전에 배웠던 방법을 써먹으려고 했는데..

다른 방법으로 응용했어야 했다.

 

 

import sys
input = sys.stdin.readline

arr = [1] * (123456 * 2)
arr[0], arr[1] = 0,0

for i in range(2,123456 * 2):
        if arr[i]:
            for j in range(i*i,123456 * 2,i):
                arr[j] = 0
while True:
    n = int(input())
    if n == 0:
        break
    else:
        print(sum(arr[n+1:n*2+1]))

먼저 n은 123,456까지 입력할 수 있고, n+1 ~ n*2안에서 찾아야 하니까 1이 123456 * 2 개 있는 배열을 만들어 준다

n*2까지 만들어주면 좋겠지만 그러면 while문 안에 넣어야 하고, 시간복잡도가 계속 늘어날 것이다...

 

그리고 arr[i]가 1이라면(True라면)  j의 배수는 모드 0으로 만들어 준다. (위에서는 2*i로 했는데 이미 i*i 이전의 소수가 아닌 수들은 0으로 되어 있기 때문에 i*i로 지정해 줘도 된다.)

 

그다음 arr의 n+1부터 n*2+1까지의 배열의 값을 모두 더해주면 n+1 ~ n*2 안에 있는 소수들의 개수가 나온다.