Python 백준 4948 베르트랑 공준 / 파이썬 알고리즘

Python 백준 4948 베르트랑 공준 / 파이썬 알고리즘

 

www.acmicpc.net/problem/4948

4948번: 베르트랑 공준

def sosu(num):
    for i in range(2, int(num ** 0.5) + 1):
        if num % i == 0:
            return False
    return True


sosu_list = []

while True:
    sosu_list.clear()
    n = int(input())
    if n == 0:
        break

    if n == 1:
        print(1)

    if n > 1:
        for i in range(n + 1, 2 * n):
            if sosu(i):
                sosu_list.append(i)
        print(len(sosu_list))

이번엔 다행히 뻘짓 안 하고 풀었다.

 

def sosu(num):
    for i in range(2, int(num ** 0.5) + 1):
        if num % i == 0:
            return False
    return True

소수를 구하는 함수sosu()를 만든다.

2부터 받은 값의 제곱근 까지를 for문으로 돌려 나누어 떨어지면 소수가 아니므로 False값을

떨어지지 않으면 True를 return 해준다.

 

제곱근이 있다면 그 위는 더 검사를 안 해도 되기 떄문에, 소수는 이렇게 구하는게 빠르다.

 

sosu_list = []

while True:
    sosu_list.clear()
    n = int(input())
    if n == 0:
        break

소수를 담을 빈 리스트 sosu_list를 만든다.

 

while문을 사용하여,

 

반복될 때 마다 sosu_list를 비워준다.

 

그 이유는 숫자 하나를 sosu_list로 감별하고, 다시 감별해야하니 삭제시켜준다.

 

밑의 입력값은 조건에 0이 나오면 입력이 끝나는 거라 되어 있어서,

 

0이 나올 때까지 입력하는 조건이다. 만약 n이 0이라면 while문을 탈출하게 된다.

 

    if n == 1:
        print(1)

    if n > 1:
        for i in range(n + 1, 2 * n):
            if sosu(i):
                sosu_list.append(i)
        print(len(sosu_list))

만약 n이 1이라면

print(1)을 해준다.

 

이건 좀 꼼수를 부렸는데.. 어찌되었든 정답처리는 됐다.

 

처음부터 소수인 애들이 있어서, 본인을 포함시켜서 소수로 카운팅하기 때문에,

 

 밑의 for문을 n+1부터 돌아가게 해놨는데, 그럴 경우는 또 1을 입력했을 때 2를 소수로 안치기 때문에,

 

유일한 반례인 1이 올 경우는 print(1)을 하게 했다...ㅋㅋ

 

여튼 for문을 돌려 만약 함수 sosu(i)가 True를 반환하면

 

빈 리스트였던 sosu_list에 소수인 i를 append 해준다.

 

for문이 다 끝나면 sosu_list의 길이를 print해주어 해당 입력값 사이의 소수를 확인한다.