글 읽기 - 파이썬 틀린 이유를 알 수 있을까요?

kd6067 2년 전 0

m부터 n까지 리스트를 만든 후 그 중에 합성수를 빼는 알고리즘을 사용했습니다.

그러나 소수가 도출되지 않고 홀수가 도출됩니다. 이유를 알 수 있을까요? 감사합니다.

m, n = map(int, input().split())
number_list = list(i for i in range(m, n + 1))
for number in number_list:
    d = 2
    while d < (number // 2) + 1:
        if number % d == 0:
            number_list.remove(number)
            break
        else:
            d += 1
for prime in number_list:
    print(prime)

314programs 2년 전 0

라인 3에 루프에서 number가 지워지면서, 리스트가 줄어드니까 number들을 채크 못하고 number를 뛰어넘어요.

시험삼아 d를 1으로 설정하니 짝수로 변했어요.

이 알고리즘을 수정한후 재출하니까 시간초과가 나더라고요...

합성수 보다 소수가 더 적으니까, 합성수를 빼는 방법보다는 소수를 빼서 저장하는게 더 빨라요.

그리고 d 값은 제곱근을 써서 int(number**0.5) + 1로 설정하면 되요, 이 방법으로 하면 시간초과도 안걸려요.

도움이 되기를.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

파이썬 틀린 이유를 알 수 있을까요?

kd6067 2년 전 0

314programs 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말