내일배움캠프 AI/페어프로그래밍
[페어프로그래밍] 230518 소수찾기 Lv.1 | for if range
생각하는 코댕이
2023. 5. 18. 16:19
728x90
페어프로그래밍 결과 코드
# =======초기 코드==========
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을 해준다.
728x90