[4코1파] #10. 소수 찾기

gunny·2023년 1월 13일

4코1파 lv1 소수찾기 python 소수찾기 소수 찾기 소수찾기 소수찾기PYTHON 코딩테스트 코딩테스트 python 프로그래머스 프로그래머스소수찾기

코딩테스트

목록 보기

10/530

4명의 안드로이드 개발자와 1명의 파이썬 개발자의 코딩 테스트 서막 : 4코1파

★축★하★
3코1파 -> 4코1파 (코흘린 개발자 1명 추가)

Rule :

하루에 1문제씩 풀기.
한 문제당 30분씩은 고민하기.
왜 그렇게 풀었는지 공유하기.
하루라도 놓친다면 벌금은 1,000원

START :

[3코1파] 2023.01.04~ (10일차)
[4코1파] 2023.01.13~ (1일차)

Today :

2023.01.13 [10일차]

프로그래머스 LV1.
소수 찾기
https://school.programmers.co.kr/learn/courses/30/lessons/12921

문제 요약

1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.

소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
(1은 소수가 아닙니다.)

제한 사항

n은 2이상 1000000이하의 자연수입니다.

입출력 예

입출력 예 설명

입출력 예 #1
1부터 10 사이의 소수는 [2,3,5,7] 4개가 존재하므로 4를 반환

입출력 예 #2
1부터 5 사이의 소수는 [2,3,5] 3개가 존재하므로 3를 반환

문제 풀이 방법

소수 그거 그냥 일단 n에 대해서 약수 리스트 맨들어서
약수 리스트 개수가 2개 이상이면 소수 아니고,
2개 면 소수라고 판단하면 될거라고 생각했다면 경기도 오산

테스트 케이스 1,2 통과해서 톱밥ㅋ 이러고있는데
테스트 케이스 11 시간 초과로 실패 및 효율성 박살나버림

재밌네ㅋ

그래서 불필요한 아래 작업 제거하고 다시 돌림 두뇌풀가동

코드는 짧아졌는데... 테스트 12의 통과시간은 길어진...?

지금 내 수준으로 아무리 지지고 볶아도 안될 것 같음..
새럼들이 질문하기에서도 화이썬으로 효율성 박살난거 때문에 다들 와글와글

와글와글 단돈 1,200원 그러나 단종

그래서 이건 과감하게 구글링

제한 조건이 n이 2이상 1000000이하의 자연수라서,, n 값이 클수록 시간초과에 걸리게 됨.. C8... 그놈의 시간초과
해당 문제는 '에라토스테네스 체' 방식을 사용해야 하는데.. 그먼씹...

<에라토스테네스 체>

https://namu.wiki/w/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98%20%EC%B2%B4

에라토스테네스 체 안썼으면 해당 문제는 통과하기 어려움

"2배수, 3배수,...n배수를 지우다보면 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97이 남는다. 이것이 100 이하의 소수이다.

이런 방법으로 만약 n이하의 소수를 모두 찾고 싶다면 1부터 n까지 쭉 나열한 다음에(...) 2의 배수, 3의 배수, 5의 배수...쭉쭉 나누는 것이다.

일종의 노가다 방식이라 상당히 무식한 방법이긴 하지만, 특정 범위가 주어지고 그 범위 내의 모든 소수를 찾아야 하는 경우[8] 아직까지 소수들 간의 연관성(=소수를 생성할 수 있는 공식)이 나오지 않았으므로[9] 에라토스테네스의 체보다 빠른 방법이 없다.[10] 프로그래밍에도 수학적 지식이 필요하다는 걸 일깨워주는 좋은 예시."

코드 공유

def solution(n):
    answer = 0
    nums = set(range(2,n+1))
    
    for i in range(2,n+1):
        if i in nums:
            nums -= set(range(2*i, n+1, i))
            
    answer = len(nums)

    return answer

증빙