1. 소수찾기
URL : https://programmers.co.kr/learn/courses/30/lessons/12921
1.1 문제 설명
- 1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.
- 소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다. (1은 소수가 아닙니다.)
1.2 제한 조건
- n은 2이상 1000000이하의 자연수입니다.
1.3 Solution
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
%%time
def solution(n):
def solutions(n):
if n < 2:
return False
if n == 2:
return True
if n % 2 == 0:
return False
r = round(n ** 0.5) + 1
for i in range(3, r, 2):
if n % i == 0:
return False
return True
result = []
for i in range(n + 1):
if solutions(i):
result.append(i)
return len(result)
solution(1000000)
1
2
Wall time: 2.06 s
78498