[Coding Test04] n 이하의 소수 찾기. 소수 개수 찾기

 

목차

1. 문제 소개
2. 사전지식 01 제곱근함수 math.sqrt 
3. 사전지식 02 소수판별 알고리즘 
4. 사전지식 03 count함수
5. 내풀이, 다른풀이

 

 

  1. 문제 소개

문제 사이트 : https://school.programmers.co.kr/learn/courses/30/lessons/12921

 

 

 

2. 사전지식01

sqrt 함수

math.sqrt(x) 함수는 x의 제곱근을 반환합니다.
(x에 루트를 씌운 값을 반환) 

추가 정보
1. 이 함수의 결과는 float 타입입니다.
2.math.sqrt(음수)가 들어오게 된다면
ERROR 가 발생합니다

int(math.sqrt(n))
# 제 코드에서 sqrt를 사용한 것입니다. 
# math.sqrt(n)는 floating 이고
# math.sqrt(n)을 int로 감쌌으므로, 정수값으로 바뀝니다. ex)루트18을 정수값으로 ->4

참고 했던 자료 : (https://blockdmask.tistory.com/522)

 

 

 

3. 사전지식02
소수판별 알고리즘 이해

에라토스테네스의 체 방식

 

참고자료 : https://seongonion.tistory.com/43

def is_prime_num(n):
    arr = [True] * (n + 1) # 특정 수가 지워졌는지 아닌지 확인하기 위한 배열
    arr[0] = False
    arr[1] = False

    for i in range(2, n + 1):
        if arr[i] == True: # 특정 수가 지워지지 않았다면 (소수여서)
            j = 2

            while (i * j) <= n:
                arr[i*j] = False # i의 배수의 값을 False로 지워준다.
                j += 1

    return arr

arr = is_prime_num(50) # 0 ~ 50중 소수를 구하기 위한 함수

for i in range(len(arr)):
    if arr[i] == True:
        print(i, end=' ')

이 방식의 알고리즘은, 빠른 시간 내에 연산을 가능하게 해줍니다.
배수들을 False값으로 저장함으로서 
True인 소수들을 걸러내어줍니다. 
이 코드를 이해하고 나서
풀이를 작성했습니다. 

 

 

4. 사전지식03
count함수 이해

카운트 함수를 이용해서, True로 저장되어 있는
소수들의 개수를 구해보았습니다.

    return array.count(True)

참고자료 : https://redcow77.tistory.com/357

 

 

 

 

4. 내 풀이

 

import math #sqrt함수를 사용하기 위해서, math함수를 호출합니다

def solution(n):
    array = [True for i in range(n + 1)] # 0부터 n까지 정수들에 대해, 모두 True로 저장합니다
    array[0] = False 
    array[1] = False #0번째, 1번째 index인 True는 False로 바꾸어줍니다. 이미 소수가 아니니까
    for i in range(2, int(math.sqrt(n)) + 1): 
		# 만약 n이 18이라고하면, 우리는 2부터 5까지 반복문을 시작합니다.
        if array[i] == True: 
        # 2부터 5까지는 아마 True값을 저장하고 있겠죠? 
        # 2의 배수인 4,6,8,10...16,18까지는 False가 됩니다
        # 3의 배수인 6,9,12,15,18은 False가 되겠습니다.
        # 그런데, 7의 배수는 어떡하냐구요 ? 8의 배수도요 ?
		# 이미 7의 배수 14는 False입니다. 8의 배수 16도 마찬가지구요!
            j = 2
            while i * j <= n:
                array[i * j] = False
                j += 1
                # 2의 배수를 False로 저장하기 위해서, 2를 곱한 4를 False로 저장하고
                # 3을 곱한 6을 False로 저장하기 위해서 j+=1을 해서 i * j를 해줍니다. 
                # 3을 곱한 6을 False로 저장하고
                # 4을 곱한 8을 False로 저장해줍니다. 
    return array.count(True)
    	#count함수는 True인 원소들의 개수를 세어줍니다. 그걸 return하면 소수의 개수가 나오게됩니다

 

 

 

Review

아마 알고리즘이라는게 존재하는 이유??
이미 존재하는 알고리즘이라는 것도
미리 공부하신 선배님들이 새롭게 코드를 짜거나
수학, 과학에서 사용되는 기본 원리에서
나오게된 것 아닐까 하는 생각이 들었다. 

혼자서 머리를 끙끙 싸맸지만, 
구글링 해보니 이미 존재하는 알고리즘이고

그걸 이해하고, 코드를 작성하기 위해
여러 사람들의 글과, 코드들을 참고했다. 

알고리즘 & 코딩테스트
공부하시는 분들 화이팅!