Notice
Recent Posts
Recent Comments
Link
S E P H ' S
[Python] 소수찾기 본문
특정 범위 내의 소수를 판별하는 문제이다. 블로그의 에라토스테네스의 체의 설명을 보고 온다면 코드 이해가 쉬울 것이다.
def sol1(n):
sieve = [True] * (n+1)
m = int(n ** 0.5)
for i in range(2, m + 1):
if sieve[i]:
for j in range(i+i, n+1, i):
sieve[j] = False
return len([i for i in range(2, n+1) if sieve[i]])
python의 set을 이용하여 더 간결하게 코드를 작성할 수 있다.
def sol2(n):
num = set(range(2, n+1))
for i in range(2, n+1):
if i in num:
num -= set(range(2*i, n+1, i))
return len(num)
2번째 코드가 보기에는 간결하지만 수행속도, 메모리를 더 많이 소모한다. 아마 set때문이지 않을까 싶다.
'Algorithm > Programmers' 카테고리의 다른 글
[Python] 신규 아이디 추천 (0) | 2021.07.06 |
---|---|
[Python] 체육복 (0) | 2021.07.06 |
[Python] 모의고사 (0) | 2021.07.05 |
[Python] 소수 만들기 (0) | 2021.06.30 |
[Python] 시저 암호 (0) | 2021.06.25 |