02 기초 수학과 구현 - 소수 찾기

소수 찾기

 

구름이는 수열 A에 있는 수들을 합한 값을 구하기로 한다. 하지만 단순히 모든 값을 다 더하는 것은 이젠 진부하다. 대신 구름이는 수열의 앞에서 소수 번째에 위치한 값들을 모두 더하려고 한다.

수열의 값들이 주어졌을 때, 구름이가 계산한 수들의 합을 구해보자.

 

 

 

# 사용자 입력 받기
>>> input()
>>> user_input = map(int, input().split())
>>> num_list = list(user_input)


# 소수 판별
>>> def is_prime(n):
>>>     if n <= 1:
>>>         return False
>>>     if n <= 3:
>>>         return True
>>>     if n % 2 == 0 or n % 3 == 0:
>>>         return False
>>>     i = 5
>>>     while i * i <= n:
>>>         if n % i == 0 or n % (i + 2) == 0:
>>>             return False
>>>         i += 6
>>>     return True

	
# 소수 번째에 위치한 숫자만 소거하여 리스트에 담기
>>> prime_list = [num for i, num in enumerate(num_list, 1) if is_prime(i)]

# 소수 번째에 위치한 숫자들의 합 계산
>>> result = sum(prime_list)
>>> print(result)

 

 

 

 

* 챗 GPT와 함께 풀었습니다

 

소수 판별하는 코드와 소수 번째에 위치한 숫자만 리스트에 담는게 어려웠다

(그냥 얘한테 다 시켰다고 봐도 무방하다)

 

소수 판별을 왜 저렇게 하는지와 enumerate 함수의 사용법이 헷갈렸다

 

5부터 시작하여 i를 6씩 증가시키면서 반복문을 왜 작성하는지,

또한 i * i가 n을 초과하면 왜 소수가 되는지 이해가 안된다

 

 

---

해설

 

 

소수 찾기

 

 

 

# 소수 판별
>>> def is_prime(n):
>>>     if n <= 1:
>>>         return False
>>>     if n <= 3:
>>>         return True
>>>     if n % 2 == 0 or n % 3 == 0:
>>>         return False
>>>     i = 5
>>>     while i * i <= n:
>>>         if n % i == 0 or n % (i + 2) == 0:
>>>             return False
>>>         i += 6
>>>     return True

 

 

함수 동작 설명:

1. n이 1 이하일 때는 소수가 아니므로 False를 반환
2. n이 2 또는 3일 때는 소수이므로 True를 반환
3. n이 2 또는 3의 배수일 때는 소수가 아니므로 False를 반환
4. 이후, 5부터 시작하여 i를 6씩 증가시키면서 i와 i+2가 n을 나누는지 확인. 나누어 떨어진다면 False를 반환
5. 이 과정을 반복하면서 i * i가 n을 초과하면 True를 반환하여 n이 소수임을 확인

 

5부터 시작하여 i를 6씩 증가시키면서 반복문을 작성하는 이유

i에 6을 더하는 이유는 6이상의 소수는 6의 배수 +1/-1의 형태라는 규칙을 사용한 소수 판별 방법이기 때문

즉, 사실 모든 소수 후보는 가능성 있는 소수의 후보는 6n±1 형태의 수만 검사하면 된다

 

 

 

enumerate 함수

 

• enumerate(iterable, start=0) 형태
• 주어진 iterable (반복 가능한 객체)을 순회하면서 각 요소와 해당 요소의 인덱스를 쌍으로 제공
• start 매개변수: 인덱스를 시작할 숫자 지정 (기본값 0)
• enumerate은 주로 for 루프와 함께 사용
• 반복 중 현재 요소의 인덱스와 값을 얻을 때 유용

 

 

# 소수 번째에 위치한 숫자만 소거하여 리스트에 담기
>>> prime_list = [num for i, num in enumerate(num_list, 1) if is_prime(i)]

 

리스트 컴프리헨션(list = [ ]) 사용

'num_list' 리스트에서 소수 번째 위치에 있는 숫자들을 새로운 리스트 'prime_list'로 가져온다

 

 

 

 

코드 해설:

 

1. 'enumerate(num_list, 1)'는 리스트 'num_list'를 순회하면서 인덱스를 1부터 시작하여 제공
2. 'for i, num in enumerate(num_list, 1)' 은 각 요소와 해당 요소의 인덱스를 순회
3. i에는 인덱스, num에는 리스트 'num_list'의 요소가 할당
4. 'if is_prime(i)'는 현재 인덱스 i가 소수인지를 확인하는 조건
5. 조건을 만족하는 경우, 이 요소를 리스트  'prime_list'에 추가

 

 

 

 

 

 

 

 

 

다른 방법 (구름 코드 해설)

 

 

# 어떤 수 N이 소수인지 판정
# 1과 N 사이에 있는 수들 중, N의 약수인게 있으면 소수가 아니다
>>> is_prime = 1

# 2부터 N-1까지의 숫자를 반복적으로 확인
>>> for i in range(2, N):
>>>     if N % i == 0:
>>>         is_prime = 0

 

 

 

코드 해설:

 

is_prime = 1

is_prime 변수를 초기화 (초기값 1로 설정)

이 값을 나중에 사용하여 N이 소수인지 아닌지를 나타냄

 

• 1: "소수가 맞다"를 의미
• 0: "소수가 아니다"를 의미

 

 

 

for i in range(2, N)

 

for 루프를 사용하여 2부터 N-1까지의 숫자를 반복적으로 확인 (N의 약수인지를 확인)

 

 

 

 

    if N % i == 0:
        is_prime = 0

 

각 숫자 i에 대해,

• N을 i로 나누었을 때 나머지가 0이면(N % i == 0), N은 i의 약수 (소수가 아님)
• is_prime 변수의 값은 여전히 1이면, 나머지가 0이 아니므로 N은 소수

 

 

 

 

큰 수에 대해서는 비효율적일 수 있으며, 효율적인 소수 판정 알고리즘 사용 추천!