Python 공부 일지 - 소수 구하기에 대하여

나는 지금 링크 속 책과 친구가 빌려준 책과 함께 Python을 공부하고 있다!!

 

 

오늘은 링크 속 책에 등장하는 연습문제 소수 구하기에 대해 이야기하려고 한다!!

https://wikidocs.net/93898

4.2.4 연습 문제: 소수 구하기

 

 

 

 

 

 

 

---

 

 

 

기본적으로 소수는 1과 자신을 제외한 약수가 없는 것을 의미한다!!

 

👉 즉, 2부터 n까지의 수 중 소수를 구하기 위해서는 각각의 배수들을 삭제해주면 된다!!!

 

 

 

그러면 Python으로 간단하게 알고리즘을 작성하기 전 알아야 할 개념들이 있다!!

 

 

먼저 Python는 Java와 달리 For문이 조금 특이하다는 것이다!

 

Java는 보통 아래와 같이 for문에서 변수는 index를 의미한다.

for(int i = 0; i< max; i++){
	System.out.println("i : " + i);
}

 

하지만 Python은 foreach같은 개념으로 해당 객체를 가져온다!!

for x in list :
	print(x)

 

그렇기 때문에 index 같이 표현하고 싶다면 특별한 함수 range()를 사용해줘야 한다!

for i in range(0,max) :
	print("i : " , i)

 

 

공부를 하기 전에 막연하게 Python 함수들을 봤을 때는 for문을 잘 알지 못해 이 부분에 대해서 애를 많이 먹었다!!

 

 

 

 

 

 

---

 

 

 

그럼 이제 진짜 소수 구하기로 넘어가보자!!

 

지금부터는 알고리즘 문제로 넘어가게 된다!

소수를 구하는 방법은 여러 가지가 존재한다!

 

 

원래 기본적인 코드로는 

def is_prime_num(n):
    for i in range(2, n+1):
        if n % i == 0:
            return False
    
    return True

 

 

 

 

하지만, 이 중 지금까지 본 것 중 가장 효율적이라고 느꼈던 개념과 함께 코드를 소개하고자 한다!

물론 이 코드는 내가 작성해낸 코드는 아니다.. 구글링을 해서 알게 된 코드다..

구글링 쵝오👍

 

 

 

 

 

아무튼, 그래서 효율적인 개념은 바로 약수의 특징이다!!

 

 

특정 수 N의 약수들을 일렬로 나열했을 때 그중 가운데의 수를 중심으로 약수가 대칭된다는 것

 

 

이를 토대로 함수를 만들게 되면, 

def is_prime_num(n):
    for i in range(2, int(math.sqrt(n))+1):
        if n % i == 0:
            return False
    
    return True

 

 

이렇게 된다!! O(n)이었던 함수가 O(n/2)으로 확 줄게 되는 것이다!!

 

 

 

 

 

---

 

 

 

약수의 특징은 꽤나, 흥미로운 개념이다!

 

이걸 고려해서 진짜 소수를 구하는 함수를 작성해보면,

 

import math

def is_prime_num(n):
    list_num = list(range(2,n))

    for i in range(2, int(math.sqrt(n)+1)):
        j = 2
        while (i * j) <= n:
            list_num.remove(i*j)
            j += 1

    return list_num

 

가 된다!!

 

 

 

 

꽤나 놀라운 개념을 알게 되었다!!

 

이걸 몰랐으면 엄청 헤맸을 것 같다..

사실 오랜만에 해보는 소수 구하기에 꽤 많이 헤맸다..

값이 제대로 나오지 않아서 조금 눈앞이 아찔했다.. ㅎ,,

 

 

 

 

아무튼 이렇게 해서 소수 구하기를 마무리한다!!!

 

 

 

 

 

 

 

 

 

---

오랜만에 하는 알고리즘과 새로 보는 파이썬은 쉽지 않다..

헷갈리는 문법 속에서 살아남기 조금 아찔하다!..ㅎ

 

다음에는 튜플에 대해서 공부해보려고 한다!

 

그럼 안녕!!!.🙌🙌🙌🙌🙌🙌🙌🙌🙌🙌🙌🙌🙌🙌