Posts 소수찾기 [Python]
Post
Cancel

소수찾기 [Python]

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
This post is licensed under CC BY 4.0 by the author.