백준 4948번 파이썬

iillyy·2021년 3월 15일
0

알고리즘

목록 보기
9/13
post-thumbnail


백준 4948번 베르트랑 공준

이번 문제는 n 부터 2n까지 소수를 구하는 문제 입니다.

백준 1929번 소수 구하기

이 문제는 위의 소수 구하기 문제에서 범위를 한정하는 것만 추가된
문제입니다.
해당 문제를 풀었을 때에는 x**0.5 로 루트 씌우는 걸 활용하요
제곱근외에 다른 약수가 없는 경우 출력하는 방법으로 풀었습니다.

이번에도 그와 같은 방식으로 풀었고,
문제에 추가된 것과 같이 범위를 추가하였습니다.

def sosu(x):
    if x ==1:            #1은 모든 수의 약수이기 때문에 pass
        return False
    for i in range(2,int(x**0.5)+1):  #제곱근이 있는 수 중에
        if x%i==0:					#약수가 있으면 false	
            return False
    return True						#이외에는 소수



while True:
    n = int(input())				#범위를 주기 위한 입력
    count=0
    if n == 0 :						#0 입력하면 아웃되는 게 조건
            break
    for i in range(n,2*n+1):		#n과 2n+1사이에서
        if sosu(i):					#sosu함수안에 있는 게 있다면
            count+=1					#카운트를 세라
    print(count)		#개수를 출력하는 조건에 맞춰 카운트를 출력

처음에는 이런 식으로 모든 소수를 구하고 입력 받은 n값 안에서의
소수를 찾게 했는데 시간 초과가 떴습니다.
크게 손보지 않는 한에서 해결 방안은 모든 소수가 아닌
문제에서 제한한 범위 1 <= n <=123,456 안에서의 소수만 저장하고
for 문을 돌리는 동안 소수 리스트에 있는 소수들을 꺼내오는 방식으로
풀었습니다.

def sosu(n):
    if n ==1:
        return False
    for i in range(2,int(n**0.5)+1):
        if n%i==0:
            return False
    return True							#소수 구하는 방식은 위와 같다

all_list = list(range(2,246912))		#문제에서 제한한 범위
memo = []								#for문 밖에 리스트 정의

for i in all_list:						#2부터 2*123,456 범위
    if sosu(i):							#sosu함수에 해당하면
        memo.append(i)					#리스트에 추가

n = int(input())

while True:
    count=0					#갯수를 세야하는 조건 때문에 카운트
    if n == 0 :
            break
    for i in memo:			#memo리스트 중에서
        if n < i <=2*n:		#입력한 값의 범위 내에서 값이 있으면
            count+=1		#있을 때 마다 카운트 +1
    print(count)
    n = int(input())		#0 입력받기 전까지 계속 해야하므로 입력 받음

0개의 댓글