Algorithm, Python n 이하의 모든 소수를 찾는 코드 (에라토스테네스의 체 알고리즘)

개념 출처 : chatGPT

코드 출처 : 이전에 다른 언어로 내가 작성해 뒀던 거 참고

- chatGPT는 최고의 선생님이다.

- 그래도 문법에 관한 거 말고 공통적인 알고리즘 개념 같은 건 아직 대학생 때 썼던 책을 찾아보는 게 더 편하다.

- 한 번 읽어봤던 거라 이해가 잘 된달까... 쩝

- 백준 풀다보니까 모르는 게 참 많다 싶다 😣😭😭😭

- 그래도 뭔가 맨날 풀어본 거 / 공부 한 거를 혼자 적어보니까 기억에 남긴 하는 것 같다

에라토스테네스의 체

- 에라토스테네스의 체는 소수를 찾는 가장 오래되고 효율적인 알고리즘 중 하나

- 특정 범위 내에서 모든 소수를 찾기 위해 사용된다.

- 적당히 작은 숫자는 일일이 검사하는 게 더 나은 것 같다. 코드 넘 길어 - 0 -

- 주요 아이디어는 특정 숫자의 배수를 반복적으로 제거함으로써 소수만을 남기는 것.

def sieve_of_eratosthenes(n):
	# 모든 숫자를 소수로 가정한다.
    # 1부터 n까지 전부 소수 => True로 추기화
    prime = [True for _ in range(n+1)]
    p = 2
    
    # 루트 n까지만 검사한다.
    # 이 범위에 대해서 말로 설명하기가 어렵다 음...
    # 해당 수(p)의 제곱값 까지 생각... 
    while (p * p <= n):
    	# p가 소수인 경우
        if (prime[p] == True):
        	# p의 배수들은 소수가 아님.
            for i in range(p * p, n+1, p):
                prime[i] = False
        p += 1
    primes = []
    for p in range(2, n+1):
    	# True인 값들 (소수인 값들)
        if prime[p]:
        	# 수집!
            primes.append(p)
    return primes

n = int(input("Enter the number: "))
primes = sieve_of_eratosthenes(n)
print(f"Primes less than or equal to {n}: {primes}")

- n = int(input(...))을 통해 사용자에게 n값을 입력받는다.

- sieve_of_eratosthenes() : 에라토스테네스의 체를 사용하여 n 이하의 모든 소수를 찾음.

 -> 여러 개 찾는 거니까 list 형태로 반환.

- prime = [True for _ in range(n+1)] : n까지의 숫자들을 다 소수인지 검사 할 건데 일단은 다 소수라고 가정.

- while (p * p <= n) : 루트 n까지만 검사하면 된다. p가 2부터 3, 4, ... 점점 커지면서 하나하나 검사할 거 니까 어차피 전부 검사되는 거나 마찬가지다. 2면 2*2 (4)까지 검사, 3이면 9까지... 나의 말주변으로는 설명하기가 어렵다. 

- if (prime[p] == True) : 만약 p가 소수라면 그 배수들은 모두 소수가 아니라고 표시.

- for i in range(p * p, n+1, p) : p의 제곱부터 시작해서 p의 배수들을 순회시킨다(step 값이 p니까 p*p부터 p간격으로 검사). p의 제곱보다 작은 배수들은 이미 이전 소수들에 의해 처리되어 있음!

- primes.append(p) : 최종적으로 True로 남아 있는 숫자들이 소수이니까 그 위치인 p를 리스트에 추가하여 반환한다.

 

오늘 공부는 여기까지... 사실 예전에 c++로 다 짜 보기도 했던 건데 증말 처음 보는 기분이다 ㄴ(ㅇ0ㅇ)ㄱ