[프로그래머스 lv.1] 소수 찾기 (건너뛴 문제 다시풀기)
문제
1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.
소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
(1은 소수가 아닙니다.)
제한 조건
- n은 2이상 1000000이하의 자연수입니다.
예전 풀이
생각
(저장 x)
코드
(저장 x)
다시 생각해보기
생각
1~n까지 도는 for문
그 안에 1~i까지 도는 for문
i를 j로 나눈 나머지를 리스트에 append
해당리스트의 길이가 2일 경우 answer += 1
코드
def solution(n):
answer = 0
for i in range(1, n+1):
list_ = []
for j in range(1, i+1):
if i % j == 0:
list_.append(j)
if len(list_) == 2:
answer += 1
return answer- 시간 초과로 정확성 56.3, 효율성 0.0
2차 시도
def solution(n):
answer = 0
for i in range(1, n+1):
remain = 0
for j in range(1, i+1):
if i % j == 0:
remain += 1
if remain == 2:
answer += 1
return answer- 혹시 리스트 만들고 append하는 것을 빼면 시간 복잡도가 조금이라도 줄어들까 싶어 정수형 변수를 설정하고 거기에 +1 하는 방식으로 바꿔봤지만 똑같다
다른 사람 풀이
import math
def isPrime(n):
for i in range(2, int(math.sqrt(n))+1):
if n % i == 0:
return False
return True
def solution(n):
answer = 0
for i in range(2, n+1):
if isPrime(i) == True:
answer += 1
return answer코드 스스로 해석하고 이해하기
- import math : 파이썬 표준 라이브러리. 수학적 연산과 관련된 기능 제공
- isPrime이라는 함수를 정의하여 소수를 판별하는 기능을 한다
- 2부터 n의 제곱근까지 for문을 돈다.
- 만약 n이 i로 나누어떨어진다면 false를 반환한다. 즉 소수가 아니라는 뜻
- 만약 해당 범위 내의 어떤 수로도 n이 나누어떨어지지 않으면 n은 소수이다.
= 모든 수는 1로 나누어 떨어지기 떄문에 2부터 시작한다
= 제곱근을 기준으로 짝을 짓는 약수가 있기 때문에 제곱근까지만 검사해도 된다(효율성 증가)
= 제곱근 이하의 어떤 수로도 나누어떨어지지 않으면 소수이다. (범위에 제곱근도 포함)
- solution함수 내에서 2부터 n까지의 범위를 for문을 돈다
- 1은 소수가 아니기 때문에 애초에 제외
- solution에서 isPrime을 통해 검사를 하고 True가 반환될 경우 answer에 1을 더해준다
** 에라토스테네스의 체 **
대량의 소수를 한꺼번에 판별할 때 사용
소수를 판별할 범위만큼 배열을 할당해 그 인덱스에 해당하는 값을 넣어준다.
1. 배열을 생성하여 값을 초기화
2. 2부터 시작해서 특정 숫자의 배수에 해당하는 숫자들은 모두 지움
(그 특정 숫자는 제외. 예를 들어 2의 배수에 해당하는 숫자를 지운다면 2를 제외한 모든 수를 지움)
3. 이미 지워진 숫자의 경우 건너뜀
4. 2부터 시작해 남은 숫자들 출력
--------------------------------------------------------------------------------------------------------------------
1. 2부터 n까지의 모든 숫자를 나열한다
2. 가장 작은 소수인 2를 선택하고 그 배수를 모두 지운다
3. 남아 있는 숫자 중 가장 작은 수를 선택하고 그 배수를 모두 지운다
4. n의 제곱근에 도달할 때 까지 3번의 과정을 반복한다
def solution(n):
answer=0
# 1. 배열을 생성하여 값을 초기화 한다. 모든 수가 소수(True)인 것으로 초기화,
array=[True for i in range(n+1)]
# 약수의 성질에 따라 가운데 약수(제곱근)까지만 확인해도 됨
for i in range(2,int(n**(1/2))+1):
if array[i]==True: # i가 소수인 경우
# 2. 특정 숫자의 배수에 해당하는 숫자들을 지운다. (i를 제외한 모든 배수를 지우기)
j = 2
while i * j <= n:
# 배수들을 지워주는 과정
array[i*j] = False
j += 1
# 4. 남아있는 숫자들(True값인 것들만) 개수를 세준다.
for i in range(2,n+1):
if array[i]:
answer+=1
return answer코드 스스로 해석하고 이해하기
- array=[True for i in range(n+1)]는 리스트 컴프리헨션을 이용해 n+1 길이의 리스트를 생성하고 모든 값을 True로 초기화한다
= True는 해당 인덱스의 숫자가 소수임을 나타냄
** 리스트 컴프리헨션 **
- 파이썬에서 리스트를 생성하는 표현 방법
- 기본적인 반복문과 조건문을 사용해 한 줄로 간단히 리스트를 만든다
- 기본 구조: [expression for item in iterable if condition]
- expression: 결과 리스트에 포함될 각 요소의 값을 정의하는 부분
- item: iterable에서 순착적으로 가져온 개별 요소를 나타내는 변수
- iterable: 순회 가능한 객체. for문을 통해 하나씩 요소를 가져옴
- condition(선택): 리스트에 포함될 요소를 필터링하는 조건
- 2부터 n의 제곱근까지 숫자를 순회한다.
- 소수 판별 시 제곱근까지만 검사해도 충분
- 만약 i가 소수라면 (array[i]가 True라면)
- 배수를 구하기 위한 초기값 j를 2로 설정한다
- i의 배수가 n을 넘기지 않는 동안 반복한다 (j+=1을 통해 j를 증가시켜가며 검사)
- i의 배수를 False로 설정하여 소수가 아님을 표시
- 2부터 n까지 모든 숫자를 순회하면서
- 만약 array[i]가 True라면(i가 소수라면)
- answer에 +1을 해준다