[프로그래머스] Level1 | 소수 찾기 - 파이썬(Python) | 연습문제

https://programmers.co.kr/learn/courses/30/lessons/12921

코딩테스트 연습 - 소수 찾기

프로그래머스에서 level 1 연습문제 소수찾기 문제를 풀었다.

레벨1이라고 만만하게 봤다가 진짜진짜 겨우 풀었다 ㅋㅋ..

---

소수찾기는 '에라토스테네스의 체' 라는 방법으로 구현을 할 수 있다고 한다.

나 이관데.. 왜 에라토스테네스의 체가 낯선지 모르겠다... 🤦‍♀️에라토스테네스의 체를 이해해도 이를 코드로 구현하는 건 정말 어려웠고 결국 구글링의 힘을 빌려 겨우 해결했다.

 

참조한 에라토스테네스의 체를 파이썬으로 구현한 코드 : https://wikidocs.net/21638

2. 소수 구하기 - 에라토스테네스의 체

출처 : https://wikidocs.net/21638

위의 설명을 코드로 구현하면 아래와 같다.

def solution(n) :
    
    a = [False,False] + [True]*(n-1)
    print(a)
    
    primes=[]

    for i in range(2,n+1):
        if a[i]:
            primes.append(i)
            for j in range(2*i, n+1, i):
                a[j] = False
    print(a)
    print(primes)
    return len(primes)

이 코드로 소수를 찾아낸다는게 너무 신기해서 중간중간 print로 찍어봤는데 print 결과물은 아래와 같다.

n이 5일 때와 10일 때 각각 프린터하면 나오는 결과물이다.

 

 

소수찾기는 종종 쓰이는 것 같아서 잘 기억해두고 있어야겠다.. (진짜!!!!!!)

이해를 못하면 통암기라도 해야한다고 생각한다!

---

해당 문제 풀이 코드

GitHub - YOOHYOJEONG/algorithm_practice: 알고리즘 공부 및 코딩테스트 준비