파이썬 - 소수찾기(lv.1)

문제 ) 프로그래머스 - 소수찾기(lv.1)

📌 문제 설명

1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.
소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다. (1은 소수가 아닙니다.)

 

📌 제한 사항

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

📌 입출력 예

n	result
10	4
5	3

---

️처음 생각한 방법 : 대.실.패 (시간 초과..)

✏️ 1은 소수가 아니므로 2 ~ n 사이의 값 중 소수 찾기

✏️ 1 ~ n으로 나누었을 경우 나머지가 0이면 약수!

✏️ 약수가 2개이면 소수이므로 answer에 +1

 

def solution(n):

    answer = 0
    
    # 1은 소수가 아님 -> 2부터 10까지 - 반복문
    for i in range(2, n + 1):
        cnt = 0
        for k in range(1, n + 1):
            if i % k == 0:  # 1-10으로 나누었을 때 0이 나오면 약수
                cnt += 1
        if cnt == 2:  # 약수가 2개 -> 소수
            answer += 1
    return answer

 

✏️ 에라토스테네스의 체 알고리즘

참고(https://velog.io/@seulki971227/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-Lv.1-%EC%86%8C%EC%88%98%EC%B0%BE%EA%B8%B0-Python)

 

import math

def solution(n):
    answer = 0
    array = [True for i in range(n + 1)]

    for i in range(2, int(n ** 0.5) + 1):
        if array[i] == True:
            j = 2  # 가장 작은 소수값의 배수 다 지우기(소수값 i는 제외한다)
            while i * j <= n:
                array[i * j] = False
                j += 1

    for i in range(2, n + 1):
        if array[i]:
            answer += 1
    return answer

 

파이썬으로 코테 공부한지 2주 정도 지난 시점.

아직도 모르는 게 산더미라 막막하고 아는 게 없다는 생각이 든다.

꾸준히 하루에 한 문제씩 풀어나가야겠다.

처음에는 무슨 말인지 감도 안 잡혔는데 위 블로그 코드를 계속 읽어보니 이해가 되었다.

돌머리 화이팅..