#210914 TIL

🪴 화요일 TIL🪴

 

✏️ 소수 알고리즘: 에라토스테네스의 체  

소수는 약수가 1과 자기 자신 밖에 없는 수이다. 

에라토스테네스의 체 알고리즘은 가장 작은 소수를 찾은 뒤, 그 소수의 배수는 제거하는 방식이다.

그리고 그 다음으로 작은 소수를 찾고 배수를 제거하는 것을 계속 반복한다.

 

파이썬으로 자연수 n까지의 수에서 소수를 찾을 때, 에라토스테네스의 체로 찾는다면 리스트를 사용해야다. 리스트의 크기를 n+1로 잡은 뒤, 리스트의 0과 1 인덱스를 제외하고 모두 True값을 넣어준다. 리스트를 for문으로 돌리면서 가장 작은 소수를 찾고, 배수 값의 인덱스는 모두 False로 만들어준다. 리스트에서 True의 갯수를 세면 자연수 n까지의 수에 소수가 몇 개 있는지 알 수 있다.

n = int(input())

num_list = [True for i in range(n+1)]
num_list[0], num_list[1] = False, False

for i in range(len(num_list)):
    if num_list[i]:
        for j in range(2,len(num_list)//2):
            if i * j < n+1:
                num_list[i*j] = False
                

cnt = 0
for i in num_list:
    if i:
        cnt += 1
print(cnt)

boolean은 1byte자료형이므로, 리스트의 길이가 1,000이면 약 1KB, 길이가 1,000,000이면 약 1MB를 사용한다. 대부분의 코딩테스트에서 메모리를 128MB ~ 512MB로 제한하기 때문에 입력값이 일억 단위를 넘지 않는다면 앞으로 소수를 찾을 때, 에라토스테네스의 체 알고리즘을 많이 사용할 것 같다.

 

 

---

👏오늘 한 일👏

 

🌸 엘리스코딩 프리트랙 수강

어제 부랴부랴 신청했는데, 다음날 9시에 프리트랙 수강 가능하다는 메일이 왔다. 앞으로 알고리즘 테스트도 봐야해서 아직 합격은 아니지만 할 일이 생겼다는 것만으로도 너무 기뻤다. 열심히 배워서 테스트도 잘 보고 싶다. 아자!!

🌸 백신 1차 접종

드디어 백신 맞고왔다... 팔이 너무 뻐근하다... 내일 더 아프다던데... 제발 괜찮기를... 🙏

 

---

🤗내일 다짐🤗

 

📌 엘리스코딩 프리트랙 수강

알고리즘 문제 최대한 많이 풀기!!! (거의 하루에 15개 이상...!!)

📌 자소서 쓸 기업 찾기