🔏 문제설명
1) 문제설명
소수란 약수가 1과 자기자신뿐인 수를 말합니다.
어떤 수 N이 소수인지 아닌지 판별하는 방법은 다음과 같습니다.1 단계. i를 2부터 N-1까지 1씩 증가시키며 다음을 수행합니다. 1-a 단계. i가 N을 나누어 떨어뜨리면 반복을 종료합니다. 1-b 단계. i가 N을 나누어 떨어뜨리지 못하면 다음 반복을 진행합니다. 2 단계. 1 단계의 반복이 종료되면 다음 두 조건을 검사합니다. 2-a 단계. 1 단계의 반복이 1-a 단계에서 종료됐다면 N은 소수가 아닙니다. 2-b 단계. 1 단계의 반복이 모든 반복을 수행하고 종료됐다면 N은 소수입니다.정수들이 담긴 리스트
num_list가 주어질 때, 리스트의 원소가 소수이면 True, 소수가 아니면 False를 차례로 담은 리스트를 return 하는 solution 함수를 완성해보세요.2) 제한사항
- 1 ≤ num_list의 길이 ≤ 100
- 2 ≤ num_list의 원소 ≤ 1,000
3) 입출력 예시
🔐 나의 풀이
🔑 접근
소수판별 알고리즘 문제는 공부하면서 한번씩 보이는 문제이기 때문에 그리 어렵진 않다. 방법도 여러가지가 있는데, 에라토스테네스의 체를 사용하는 것과 그냥 하나씩 집어넣어보는 방법이다. 이 때, 범위를 √ n 으로 하면 시간 복잡도를 줄일 수 있다.
- 에라토스테네스의 체
- 2부터 소수인지 판별하고자 하는 수 (N)까지 나열한다.
- 2는 자명하게 소수이다.
- 2가 소수이므로 2의 모든 배수는 합성수이다. 나열한 수 중 2의 배수를 모두 지운다.
- 3은 자명하게 소수이다.
- 3이 소수이므로 3의 모든 배수는 합성수이다. 나열한 수 중 2의 배수를 모두 지운다.
- 위의 방법을 √ N 이하의 모든 소수들에 대해 시행한다.
- 지워지지 않은 수들은 모두 소수이다.
🔑 나의 코드 - 1
- 수를 대입하여 확인하기
def check1(n): #수를 대입하여 소수인지 판별
m = int(n ** 0.5)
for i in range(2, m+1):
if n % i == 0:
return False #√n 이하의 수중 n을 나눌 수 있는 수가 있다면 n은 합성수
return True #√n 이하의 수중 n을 나눌 수 있는 수가 없다면 n은 소수
def solution1(num_list):
answer = []
for num in num_list:
answer.append(check1(num)) #num_list의 원소가 소수이면 True, 아니면 False를 answer에 추가
return answer🔑 나의 코드 - 2
- 에라토스테네스의 체 활용
def check2(n): #에라토스테네스의 체
eras = [True] * n #에라토스테네스의 체 생성
m = int(n ** 0.5)
for i in range(2, m + 1):
if eras[i] == True: #i가 소수일 떄
for j in range(i+i, n, i):
eras[j] = False #i의 배수는 모두 합성수
return [i for i in range(2, n) if eras[i] == True] #소수들의 모음
def solution2(num_list):
primes = check2(1000) #1000(제한사항)에 대해 에라토스테네스의 체 적용
answer = []
for num in num_list:
if num in primes:
answer.append(True) #에라토스테네스의 체 결과로 소수로 판명된 목록에 있다면 answer에 True 추가
else:
answer.append(False) # 없다면 answer에 False 추가
return answer🔓 결과
- 1번 코드
- 2번 코드
.