[4948] 베르트랑 공준 / 파이썬 (에라토스테네스의 체,리스트컴프리핸션)

 

문제 링크: https://www.acmicpc.net/problem/4948

 

4948번: 베르트랑 공준

---

❌ 1차시도 실패

#시간초과(약수성질 소수판별 알고리즘이용)----------------------
def sosu(x):
    for i in range(2, int(x**0.5)+1):
        if x % i == 0:   
            return False
    return True
 
from sys import stdin
while True:
    n=int(stdin.readline())
    cnt=0
    if n==0:
        break
    elif n==1:
        print(1)
    else:
        for x in range(n,2*n+1):     
            if sosu(x):
                cnt+=1
        print(cnt)

시간초과.....................데쓰요..

약수의 성질을 이용한 소수알고리즘 가지고는 역부족이었나보다...

---

❓ 정답은 ??

#성공(에라토스테네스의 체 이용)---------------------------
def sosu(x):
    array=[True for _ in range(x+1)]
    for i in range(2,int(x**0.5)+1):
        if array[i]==True:
            j=2
            while i*j<=x:
                array[i*j] = False
                j+=1
    return [i for i in range(2,x) if array[i]==True]
    #array 인덱스를 가지고 소수리스트를 return하기 = result
 
while True:
    n= int(input())
    if n==0:break
    result=sosu(2*n+1) #1) 먼저 2n까지 소수를 구하기
    print(len([i for i in result if i>n])) #2) n보다 큰 조건만족 소수 개수구하기

---

💯 풀이 과정

1) 먼저 에라토스테네스의 체를 이용하여 2n까지 소수들 리스트를 만들어 return하고

(**에타토스네스의 체는 여기를 참고👇👇👇)

2021.11.10 - [코딩공부/파이썬 공부] - [샛길공부] 소수판별,에라토스테네스의 체(feat. 이코테 유튜브강의)

2) return 된 리스트를 result로 할당하고

3) for반복문 + if i>n 보다 큰 아이들의 컴프리핸션을 하여 len을 출력한다.

---

😎오늘의 한줄평: 너무나도 복잡쓰, 어려운 문제이기에 내일 한번 다시 풀어보기!!!!!⭐⭐⭐