인프런 커뮤니티 질문&답변
작성한 질문수
시간 복잡도(7.소수의 개수(에라토스테네스 체))
작성
·
168
·
수정됨
0
안녕하세요
해당 문제의 답을 스스로 작성해보았는데요
이렇게 했더니 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)답변 1
0
안녕하세요, 인프런 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의 크기가 커져도 효율적으로 소수를 찾을 수 있습니다.