시간 복잡도(7.소수의 개수(에라토스테네스 체))

Question

안녕하세요 해당 문제의 답을 스스로 작성해보았는데요 이렇게 했더니 n의 숫자가 작을 때는 잘 작동 되지만 숫자가 커지면 작동이 안됩니다. 선생님의 코드처럼 이중 for문을 사용했는데 선생님의 코드는 잘 작동이 되고 제 코드는 잘 작동이 되지 않습니다.. 선생님의 코드는 배수를 활용해서 더 빠를 것이라고 생각이 되긴 하는데, 제 코드를 어떻게 수정하면 좋을까요 n = int(input()) cnt =[0] * (n+1) count =0 for i in range(1,n+1): for j in range(2,n+1): if i % j == 0: cnt[i] = cnt[i] + 1 if cnt[i] == 1: count = count +1 print(count)

인프런 AI 인턴 · Answer

안녕하세요, 인프런 AI 인턴입니다. 해당 문제에서는 에라토스테네스의 체 알고리즘을 사용하여 효율적으로 소수를 구하는 것이 포인트입니다. 고서현님의 코드를 보면 각 숫자에 대해 1부터 n+1까지 나눠보면서 소수를 판별하고 있습니다. 이러한 방법은 시간 복잡도가 높기 때문에 n의 크기가 커질수록 더 많은 시간이 소요됩니다. 고서현님의 코드를 에라토스테네스의 체 알고리즘을 사용하여 개선하려면, 다음과 같이 작성할 수 있습니다: n = int(input()) prime = [True] * (n + 1) count = 0 for i in range(2, n + 1): if prime[i]: # i가 소수일 경우 count += 1 for j in range(i*2, n + 1, i): prime[j] = False # i의 배수들은 소수가 아님 print(count) 이 코드는 먼저 모든 숫자를 소수로 가정하고 시작합니다. 그리고 2부터 시작하여, 각 숫자가 소수일 경우(count를 증가시키고), 그 숫자의 배수들을 모두 소수가 아니라고 표시합니다. 이때, 가장 중요한 점은 i의 배수를 표시할 때 i*2부터 시작하며, 그 이후로 i의 배수만큼 증가시키며 표시한다는 것입니다. 이 알고리즘을 사용하면 불필요한 나눗셈 연산을 줄이고, n의 크기가 커져도 효율적으로 소수를 찾을 수 있습니다.