백준 정리 #2

에라토스테네스의 체 설명은 여기에 잘 되어있음 감사합니당

• 백준 1929번
  M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.

import sys
import math

def isPrime(num) :
    for i in range(2, int(math.sqrt(num))+1) :
        if num%i == 0 :
            return False
    return True

a,b = map(int, input().split(" "))

for i in range(a, b+1) :
    if isPrime(i) :
        print(i)

먼저 수를 집어 넣으면 소수인지 여부를 판단해주는 함수를 만든다.
이때 2부터 num까지 다 돌리면 시간이 너무 오래 걸리기 때문에
num의 제곱근까지 돌리면 된다!

그리고 주어진 범위에서 수를 하나씩 집어 넣으면서 소수를 구분하면 된다.
1929번 기반으로 4948번을 풀어보자.

• 백준 4948번
  자연수 n이 주어졌을 때, n보다 크고, 2n보다 작거나 같은 소수의 개수를 구하는 프로그램을 작성하시오.

처음에는 아래와 같이 코드를 작성했다.

import sys
import math

def isPrime(num) :
    for i in range(2, int(math.sqrt(num))+1) :
        if num%i == 0 :
            return False
    return True

def countPrime(num) :
    count = 0
    for i in range(num, 2*num +1) :
        if(isPrime(i)) :
            count+=1
    return count

while True :
    a = int(input())
    if a == 0 :
        break
    elif a == 1 :
        print(1)
    else :
        print(countPrime(a))

결과는 시간초과
countPrime() 함수에서 n부터 2n까지 다 돌아가면서 소수를 찾는 게 오래 걸려서 시간 초과 결과가 나왔다.

import sys
import math

def isPrime(num) :
    if num == 1 :
        return False
    for i in range(2, int(math.sqrt(num))+1) :
        if num%i == 0 :
            return False
    return True
list_num = []

for i in range(2, 246913) :
    if isPrime(i) :
        list_num.append(i)

while True :
    a = int(input())
    count = 0
    if a == 0 :
        break
    for i in list_num :
        if a < i <= 2*a :
            count+=1
    print(count)

수정한 코드는 아예 2부터 123,456 * 2 한 값까지 소수를 다 구해서
list_num이라는 리스트에 넣고 주어진 범위에 해당하는 소수의 개수를 구하도록 하였다.
물론 이것도 검색을 통해서 조언을 얻고,, 다들 똑똑하다 증맬루