시간 복잡도(7.소수의 개수(에라토스테네스 체))
243
작성한 질문수 1
안녕하세요
해당 문제의 답을 스스로 작성해보았는데요
이렇게 했더니 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의 크기가 커져도 효율적으로 소수를 찾을 수 있습니다.
기존에 윈도우 10으로 잘 써왔는데 윈도우 11로 바꾸고 나서 채점이 안됩니다.
1
78
2
스택에서 ')'을 만나는 경우
0
79
3
문제가 어디있나요?
0
67
2
변수 or 함수명
0
61
1
침몰하는 타이타닉 문제 질문입니다
0
57
1
AA.py 책점 에러
0
60
1
오늘 구매했는데 파이썬 자료구조 궁금한거 있으면 답변이 잘 될까요.
0
111
2
5.동전분배하기 문제 밑에코드도 정답이될까요?
0
110
1
아나그램 비교 코드
0
116
2
AA.PY파일 복사 후 채점 진행할때 오류 발생합니다.
0
161
2
문제 링크가있나여?
0
147
2
채점기 Time Limit Exceeded 오류 문의
1
165
2
동적계획법은 사용하는 문제
0
126
2
제 코드 좀 봐주세요
0
148
1
예외가 존재할 가능성?
0
97
1
3번이 안풀립니다
0
93
0
5번 틀림
0
115
0
오류원인?
0
98
0
리스트 선언
0
107
1
침몰하는 타이타닉(그리디) 문제 질문
0
110
1
알고리즘
0
69
1
코딩테스트
0
92
1
DFS 순서 질문드립니다.
0
129
2
left, right를 사용한 풀이법에 대한 질문입니다
0
91
1