[Python] 백준알고리즘 1929번 소수 구하기 (S2)

이번 문제에서는 M과 사이의 소수 문제를 구하는 문제이다. 소수란?

1과 그 수 자신 이외의 자연수로는 나눌 수 없는 자연수 예를 들어, 1을 제외한 2, 3, 5, 7, 11, 13...을 말한다. 따라서 위 예시 입력에서 3과 16사이의 소수를 출력하는 것이므로 3, 5, 7, 11, 13이다.

가장 쉬운 방법은 3에서 16까지의 자연수를 자기자신을 제외해서 사잇수를 모두 나눠보면 된다. 하지만!!

그렇게 하면 시간초과에 걸려 모두 나눠볼 수 는 없다. 시간을 단축하기 위해서 나눠보는 자연수의 개수를 줄이면 된다.

이를 사용하는 방법이 제곱근이다. 소수를 구할 수 있는 최대 숫자는 N 자리에 입력한 16이다. 16은 1, 2, 4, 8, 16 으로 우리는 자연스럽게 2로 나누면 8이 된다는 것을 알 수 있다.

따라서, 4까지만 나눠보면 8을 굳이 나누지 않아도 소수가 아니라는 것을 알 수 있다. 18은 1, 2, 3, 6, 9, 18 이다. 18의 제곱근은 4.2426...이다....

요청 처리 중입니다...

[Python] 백준알고리즘 1929번 소수 구하기 (S2)

등록된 다른 글