hmk run dev

백준 4948 베르트랑 공준 풀이 본문

Algorithm

백준 4948 베르트랑 공준 풀이

hmk run dev 2021. 3. 13. 20:20

www.acmicpc.net/problem/4948

 

4948번: 베르트랑 공준

베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼

www.acmicpc.net

 

정답코드

import math



def IsPrime(num): #소수인지 판별하는 함수

    a = int(math.sqrt(num)) # 루트2 루트3 루트4(2) 루트 5 루트 6

    if num == 1:

        return False

    else:

        for i in range(2, a+1):

            if num % i == 0: 

                return False

        return True



Num_list = list(range(2,246912)) #미리 뽑아 버린다 소수를

Sort_list = []

for i in Num_list: # 위에 함수에 들어갈 수를 반복문으로

    if IsPrime(i): #

         Sort_list.append(i) #소수인 것만 넣어라



while True:

    n = int(input())  #범위설정

    if n == 0:

        break

    cnt = 0

    for i in Sort_list: # 소수 뽑은 리스트를 반복문으로 하나씩 꺼낸다

        if n < i <= n*2: # 반복문으로 꺼낸수가 n과 2n 사이에 있으면

            cnt += 1 # 카운트를 1씩 올리자

    print(cnt)     


처음 틀린코드

 

매번 소수를 구할 때마다 에라토스테네스의 체를 써서 시간초과로 인해 틀렸다고 나온것 같다!

num = int(input())



sosu = []



def new_func(sosu, i):

    if(i<2):

      result = False

    for j in range(2,i):

     if(i%j==0):

      result = False

    if result:

        sosu.append(i)



for i in range(num+1, (num*2)+1):

    result=True

    new_func(sosu, i)

     

print(len(sosu))

'Algorithm' 카테고리의 다른 글

백준 28258 큐 2  (0) 2021.03.16
잡다한 글 DFS  (0) 2021.03.11
DFS & BFS  (0) 2021.03.11
Comments