[Coding Test] 프로그래머스 - 소수 찾기

[문제 설명]

1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.

소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
(1은 소수가 아닙니다.)

 

[제한 조건]

n은 2이상 1000000이하의 자연수입니다.

 

소수찾기 문제는 대체로 좋은 방법 중에 하나가 에라토스테네스의 체이다.

2부터 시작해 자연수를 차례로 쓴 다음, 2 이외의 2의 배수, 3 이외의 3의 배수, 5 이외의 5의 배수의 순서로 수를 지워나가 끝에 남는 수가 소수이다.

 

출처:네이버 지식백과

 

여기서는 에라토스테네스의 체가 아닌 범위 내의 자연수가 소수인지 아닌지 하나하나 확인하는 방법을 포스팅 하고자 한다.

---

#방법1
def solution(n):
    answer = 0
    for i in range(2, n+1):
        cnt = 0
        for j in range(2, i+1):
            if i % j == 0:
                cnt += 1
                break
        if cnt == 0:
            answer += 1
    return answer

# 방법1과 같이 n보다 작은 자연수의 약수의 개수를 세는 코드를 작성했으나 시간 초과로 통과되지 못했다.

 

문제 ! n이 커질 수록 시간이 더 많이 소요됨.

연산 시간을 단축시킬 idea!

1) 소수는 홀수로만 구성 >> 2의 배수 제외 >> i 자체를 3이상의 홀수(2*i+1)로 만들어 연산범위를 절반으로 줄이기

2) 나누어 떨어지지 않음 >> 2다음으로 큰 소수인 3으로 나누어 떨어지지 않는지 확인

# 방법2

def solution(n):
    answer = 1	# n이 2인 경우를 포함하여 answer 초기값 1로 설정  
    for i in range(1, n//2):	# n보다 작은 짝수 제외
        i = i*2+1		# i는 3보다 큰 홀수로 설정
        if(i == 3):		# i가 3일 경우 카운트
            answer += 1
            continue
        elif(i % 3 == 0):	# 3의 배수는 제외
            continue
        elif(i % 3 != 0):	# 3의 배수가 아니면 약수의 개수 확인
            cnt = 0
            for j in range(2, int(i**0.5)+1):	#자연수 i의 약수를 루트i 범위에서 구함.
                if i % j == 0:
                    cnt += 1	#i로 나누어 떨어지는 수가 1개라도 있으면 반복문 멈춤.
                    break
            if cnt == 0:
                answer += 1
    return answer

 

첫번째 for문에서 n//2로 연산 범위를 절반으로 줄여 시간 초과를 피하긴 했으나 에라토스테네스의 체로 구한 것보다 훨씬 비효율적이다.

다만, 반복문을 돌릴 때 i를 홀수(혹은 특정한 수로 한정하여) 연산 범위(n)를 줄이는 방법을 사용했다는 것에 의의를 두고 포스트에 올린다.

 

문제 설명문제