<문제>
1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요. 소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다. (1은 소수가 아닙니다.)
<제한 조건>
n은 2이상 1000000이하의 자연수입니다.
< 풀이 1단계>
def solution(n):
answer = []
for i in range(2,n+1):
arr = []
for j in range(1,i+1):
if i%j == 0:
arr.append(j)
if len(arr) == 2:
answer.append(i)
del arr
return len(answer)
< 풀이 2단계>
def solution(n):
li = []
for n in range(2,n+1):
check = True
for i in range(2, int(n**0.5)+1):
if n%i == 0:
check = False
if check:
li.append(n)
return len(li)
< 풀이 3단계>
def solution(n):
numbers = [True] * (n + 1)
cnt = 0
for i in range(2,int(n**0.5)+1):
if numbers[i] == False:
continue;
for j in range(2*i,n+1,i):
numbers[j] = False
for j in range(2,n+1):
if numbers[j] == True:
cnt+=1
return cnt
<다른 풀이>
def solution(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)
<풀이 3단계 코드 설명>