[페어프로그래밍] 230518 소수찾기 Lv.1 | for if range

소수찾기

---

페어프로그래밍 결과 코드

# =======초기 코드==========
def solution(n):
    
    def prime_number(number):
        for i in range(2,int(number**0.5)+1):
            if number % i == 0:
                return False
        return True
    answer = 0
    for num in range(2,n+1):
        if prime_number(num):
            answer += 1
    return answer

+테스트용 전체 코드

# https://school.programmers.co.kr/learn/courses/30/lessons/12921

import os, time
os.system("cls")

# 1~n 사이의 숫자를 반복문으로 분리
# 소수인지 판별
# 소수라면 카운트+1
# 카운트 return

# =======초기 코드==========
def solution(n):
    
    def prime_number(number):
        for i in range(2,int(number**0.5)+1):
            if number % i == 0:
                return False
        return True
    answer = 0
    for num in range(2,n+1):
        if prime_number(num):
            answer += 1
    return answer

# =======테스트공간==========
a=5
b=10
c=2
d=1000000

print("3 : ",solution(a))
print("4 : ",solution(b))
print("1 : ",solution(c))
print("78498 : ",solution(d))

---

리팩토링 코드

# 리팩토링 | bool type의 특성을 고려해 0,1 을 활용. if문 제거
def solution(n):
    def prime_number(number):
        for i in range(2,int(number**0.5)+1):
            if number % i == 0:
                return False
        return True
    answer = 0
    for num in range(2,n+1):
        answer += prime_number(num)
    return answer

---

흠터레스팅 코드

# 1번 | set변환 후 연산에 활용, range step option 사용, 소수가 아닌 수들을 제거하는 형식
def solution(n):
    num=set(range(2,n+1))

    for i in range(2,n+1):
        if i in num:
            num-=set(range(2*i,n+1,i))
    return len(num)

---

시사점 or 새로이 알게된 점

+에라토스테네스의 체

# 에라토스테네스의 체
#
# 핵심은 소수의 배수를 지워나가는 것.
# 2부터 시작해서 2 4 6 8 ... 을 지우고
# 다음 소수인 3의 배수 3 9 15 ...을 지우고(6과 12는 앞에서 이미 지워짐)
# ...
# 결국 소수만 남는다.

n = 20
# 0부터 n까지 인덱스로 표현할 배열 생성
# (인덱스 매칭의 편의성을 위해 n+1개)
numbers = [True]*(n+1)  # True면 소수, 소수로 나눠지면 False로 바꿔줄 예정

# 0과 1은 소수가 아님
numbers[0], numbers[1] = False, False

# 2부터 n까지 돌면서(n의 제곱근까지만 돌아도 ok)
for i in range(2, int(n ** 0.5) + 1):
    if numbers[i]==True:  # 특정 수가 지워지지 않았다면 (소수여서)
        k = 2  # i * 1은 자기자신(소수)이므로 2부터 시작

        # i의 배수를 지워주는 작업 i*2 i*3 i*4 ... n이하의 모든 배수를 지워준다.
        while (i * k) <= n:  # i * k가 n보다 커질때까지 반복
            numbers[i*k] = False
            k += 1

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



# 왜 제곱근까지만 해도 되는지?
# n = 144(12*12)일 때,

# 2 4 6 8 ...
# 3 9 15 21 ...
# 4 pass (4는 False이므로)
# 5 25(5*5) 35(5*7) 55(5*11) ...
# 6 pass
# 7 49(7*7) 77(7*11)
# 8 pass
# 9 pass
# 10 pass
# 11 11*11 11*13 11*17 ...

# 해당 수보다 작은 소수와의 곱은 이전에 모두 지워지게 된다 ex)3*7은 3에서 다 지워져서 7에서는 고려할 필요가 없음
# 자신보다 큰 소수와의 곱만 지워주면 된다. 따라서 제곱근까지만 판별하면 소수를 모두 판별할 수 있다.

# 완성된 함수
def solution(n):
    numbers = [True]*(n+1)
    numbers[0], numbers[1] = False, False


    for i in range(2, int(n ** 0.5) + 1):
        if numbers[i]:
            k = 2

            while (i * k) <= n:
                numbers[i*k] = False
                k += 1
    return numbers.count(True)

# 흠터레스팅 1번 리팩토링 코드 
def solution(n):
    num=set(range(2,n+1))
    for i in range(2,int(n**0.5)+1): # pair_number제외
        if i in num:
            num-=set(range(2*i,n+1,i))
    return len(num)
    
# 377.47788 ms | 기존 1번 코드
# 269.62185 ms | pair_number 제외한 코드

인수의 경우 필연적으로 pair_number가 생기게 된다.
그래서 pair_number 중 하나만 판별해도 되니, 탐색범위를 √n+1 로 줄여준다.
이 때,  √n은 <float>로 나올수 있으니 int(n**0.5)을 해주고, int 과정에서 버림 처리가 되니 +1을 해준다.