내 풀이 (실패)
- 테스트 10 ~ 테스트 12 : 실패
- 효율성 : 실패
def is_prime_number(x):
for i in range(2, x):
if x % i == 0:
return False
return True
def solution(n):
answer = 0
for i in range(2, n + 1):
if is_prime_number(i) == True:
answer += 1
return answer
다른 방법
- 소수를 구하기 위해 2부터 비교하는 숫자까지 나눠가면서 나머지를 확인하는 방법이 있지만 효율성 부분에서 시간이 상당히 걸리게 됩니다.
- 여기서 에라토스테네스의 체 방법을 이용합니다. 소수인지 판별하고 싶은 수의 제곱근 까지의 배수를 제외시켜주는 방법입니다. 즉, 10을 판별하고 싶으면 10의 제곱근은 3.xxx이므로 [2 : 10] 에서 2, 3의 배수를 제외시켜주면 됩니다.
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)
'Engineering WIKI > Programmers' 카테고리의 다른 글
[프로그래머스] 이상한 문자 만들기 (0) | 2022.04.20 |
---|---|
[프로그래머스] 약수의 합 (0) | 2022.04.19 |
[프로그래머스] 시저 암호 (0) | 2022.04.19 |
[프로그래머스] 문자열을 정수로 바꾸기 (0) | 2022.04.19 |
[프로그래머스] 문자열 다루기 기본 (0) | 2022.04.15 |
[프로그래머스] 문자열 내림차순으로 배치하기 (0) | 2022.04.15 |
[프로그래머스] 문자열 내 p와 y의 개수 (0) | 2022.04.15 |
[프로그래머스] 문자열 내 마음대로 정렬하기 (0) | 2022.04.14 |