[Python/파이썬] [🥈3] 백준 알고리즘 4948 - 베르트랑 공준

📖[Python/파이썬][🥈3] 백준 알고리즘 4948 - 베르트랑 공준

📜문제

---

📕풀이방향

문제에서 주어진 범위(1 ≤ n ≤ 123,456)를 주의하자 (2n까지이므로 246,912까지..)
가장 최악의 O(N)을 생각해보자 (n=123,456이고 2n=246,912 ..)

내 포스팅 : [Python] 백준 알고리즘 1929 - 소수 구하기
전에 소수구하기 문제를 푼 적이 있는데, 이런식으로 접근하면 이번에는 시간초과🤦🏻‍♀️

우선 2n이 기준이므로 2~246,912까지 소수를 모두 list(num)에 저장하자
무한루프로 n값이 0아니면 num에 접근하여 n~2n까지 검사하면서,
소수가 존재하면 res+1를 하여 res를 출력하자

---

📝알고리즘 구현순서

1. 2~246,912까지 소수를 list(num)에 저장하기
2. 무한루프로 n==0이면 break, 아니면 num요소를 n~2n까지 검사하면서 res++ 해주기

---

💻결과코드

num = []

for i in range(2, 246913):
    cnt = 0

    for p in range(2, int(i**0.5)+1):
        if i % p == 0:
            cnt += 1
            break

    if cnt == 0:
        num.append(i)

while True:
    n = int(input())
    res = 0

    if n == 0:
        break

    for i in num:
        if n < i <= 2*n:  # if i > n and i <=2*n과 같음
            res += 1

    print(res)

---

✏️1. 2~246,912까지 소수를 list(num)에 저장하기

num = [] #빈리스트

for i in range(2, 246913):
    cnt = 0

    for p in range(2, int(i**0.5)+1): 
        if i % p == 0: 
            cnt += 1
            break #cnt가 0이 아니면 소수아님

    if cnt == 0: #cnt가 0이면 소수이므로 num에 저장
        num.append(i)

---

✏️2. 무한루프로 list(num)의 개수 출력

while True:
    n = int(input())
    res = 0

    if n == 0:  #0이면 종료
        break

    for i in num: #num요소 하나씩 검사
        if n < i <= 2*n: #i가 n보다 크고 2n보다 작은 값일때마다 res++
            res += 1

    print(res)

---

📚초기 알고리즘 오류와 정리

※초기 알고리즘

✍🏻소수구하는 함수 구현, n값 입력될 때마다 n~2n소수 검사 후 cnt++

import sys
input = sys.stdin.readline

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

cnt = 0

while True:
    n = int(input().rstrip())
    cnt = 0
    if n == 0:
        break
    else:
        for i in range(n+1,(2*n)+1):
            if gj(i):
                cnt += 1
        print(cnt)

※구현순서
  1. 소수구하는 gj()함수 만들어놓기
  2. n입력값에따라 함수를 n~2n까지 호출하여 cnt++

👉🏻 n값이 들어올 때마다 n~2n까지 소수를 계속해서 계산해야 하므로 시간초과🤦🏻‍♀️

---

1. 초기 알고리즘 설계가 매우 중요하다
   이 때까지는 모든 케이스를 브루트포스로 계산하다가 오류가 나기 일쑤였는데,
   위 문제는, 주어진 모든 케이스를 저장해두고 꺼내쓰는 것이 더 빠르다....
   👉🏻 구현 전 알고리즘 설계 과정에서 과연 어떤 알고리즘이 적합한지 판단하는 연습하자