(해결 X)백준 4948번: 베르트랑 공준 (2020/07/26)

4948번: 베르트랑 공준

어제 했던 거랑 거의 똑같은 문제네요
빨리 풀면 하나 정도는 더 할 수 있을 것 같…


문제

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

입력 예시

1
10
13
100
1000
10000
100000
0

출력 예시

1
4
3
21
135
1033
8392

시간초과 :thinking:
여기서 어떻게 더 간편하게 할까요ㄷㄷ
다 갈아엎어야하나…

정답아님
test_nums = list()  # 입력들 받아놓음
count = 0  # 반복문 횟수 변수 겸 각 항목의 소수 개수
isSosu = True

# 입력이 0이 될때까지 입력받기
while True:
    test_nums.append(int(input()))
    if test_nums[count] == 0:
        test_nums.pop()
        break
    count += 1

# test_nums 항목들에 대해 반복
for num1 in test_nums:
    count = 0

    # 선택 항목의 범위에서 반복
    for num2 in range(num1+1, num1*2+1):

        # 가능한 약수 범위에서 반복
        for num3 in range(2, int(num2/2)+2):
            if num2 % num3 == 0:  # num3으로 나눠떨어진다면
                if num2 == num3:
                    isSosu = True
                    continue
                isSosu = False
                break  # 소수 아님
            isSosu = True

        if isSosu:
            count += 1

    print(count)  # 소수 개수 출력

for num3 in range(2, int(num2/2)+2):

여기부분 num2/2보다 sqrt(num2)로 바꿔도 돼요.
한 약수가 sqrt(num2)보다 작으면 다른 약수는 sqrt(num2)보다 클테니까요.

1 Like

감사합니다 :smiley:
가장 작은 약수가 2라는 생각밖에 안하느라 이런 부분을 놓쳤네요
이제 다른 부분만 더 단축시키면 될 것 같읍니다!

쪼오끔 힌트를 드리자면, n의 최대값인 123456이 입력값으로 계속 들어온다면 123456까지 매번 소수 개수를 세야하는 불상사가 일어납니다…

1 Like
  1. 1부터 123456 사이의 소수를 구해 배열로 저장한다(정렬된 상태).
  2. 입력받을 때마다 이진 탐색으로 상한과 하한을 구한다.
  3. 상한과 하한의 거리를 출력한다.
1 Like

오늘은 실패…
중간에 포기하고 크롤러 만지작거리다가
잘 시간 거의 다 되서야 급하게 수정했는데
결국 포기하게 되었읍니다…

문제 푸는 데 힌트 주시며 도와주신 분들 감사합니다!

미련은 깔끔하게 버리고
내일부터 다시 새 문제 풀기! :sweat_smile:

파이팅입니다. ㅎㅎ
Seaurchine은 먹는 성게라는 뜻인가요?

BOJ 문제 저작권을 찾아봤습니다.

https://www.acmicpc.net/help/rule
BOJ저작권

문제는 링크로만 추가해달라고 권장하네요.
소스코드는 마음껏 올리셔도 될 것 같습니다. :slight_smile:
방송도 마음 것…


P.S.

이미 찾아 보셨더군요.
음… 입출력 예시도 문제라고 보는 것이 맞을 것 같습니다.
명시적으로 문제를 올리는 것을 제한한다는 구절이 없기 때문에, 입출력 예시는 물론 입출력 예시를 포함한 전문을 올리셔도 일단은 문제가 없을 것 같아 보이네요.
그래도 권장하고 있으니 언젠가 규칙에 명시적으로 제한하도록하는 구절을 추가한다면 일일이 수정을 해줘야 하는 작업이 발생 할 수도 있겠죠. ㅎㅎ

1 Like

안댐, 싸던건 마저싸고 가샘

1 Like

엙…
학교 갔다와서 마저 치우겠습니다…

이toRl가