[백준 파이썬] 소수 문제 유형 정복하기

파이썬 소수문제 정복하기

 

한 주간 알고리즘 스터디를 진행하면서 소수 문제를 다루었다.

 

소수가 사용되는 유형을 정리해두면 도움이 될 것 같아서 정리해보았다.

 

설명하기 쉬운 코드를 위해 유투브 영상을 일부 참고하였다.

 

성능 비교를 위해서 time을 측정하였고, input에는 동일하게 5를 넣어 비교해보았다.

 

 

소수 여부 판별

# chapter 1
# n이 소수인지 아닌지 판별_약수의 개수를 check 하여 판별

n = int(input())
check = 0

for i in range(1, n+1):          # n+1 : n까지 포함하기 위해 ; range 범위의 특성
    if n%i == 0:
        check += 1

if check == 2:
    print('소수')
else:
    print('소수가 아닌 수')


# 5
# 소수
# time :  0.7030019760131836

가장 기초적인 단계다.

 

range 범위 안의 숫자들을 나누었을 때 나누어 떨어지는(나머지가 0이되는) 값을 찾아보고,

 

발견되면 check에 개수를 더해준다.

 

소수일 경우 check의 개수는 2가 될 것이며, 합성수의 경우, 3이상이 될 것이다.

 

 

# ch. 2
# ch. 1에서 효율성을 향상시키기 위함
# range의 범위를 변경

n = int(input())
check = True

for i in range(2, n):         # 1부터 n까지(n-1 x) 체크했을 때 약수가 없는 수
    if n%i == 0:
        check = False
print(check)

# 코드가 짧아지고, 메모리가 줄어들게 됨
# 단, n은 1보다 큰 수가 되어야 함


# 5
# True
# time :  0.40419912338256836

ch.1에서 range 범위를 일부 수정해주었다.

 

range 범위에 1과 n(자신의 값)을 포함시키지 않는 대신 check 값이 0이 아닐 경우,

 

소수가 아닌 점을 이용해서 코드 성능을 개선하였다.

 

• 컴퓨터 계산에 불필요한 범위를 제거해주는 것만으로도 성능이 개선된다

 

 

# ch. 3
# 범위내의 소수 구하기_1~a 사이 모든 소수값 구하기(a>0)

a = int(input())
li = []

for n in range(2, a+1):
    check = True
    for i in range(2, n):
        if n%i == 0:
            check = False
    if check:                  # if check==True:와 동일
        li.append(n)

print(li)


# 5
# [2, 3, 5]
# time :  0.4038875102996826

ch. 1, ch.2 에서 한 단계 나아가 1~a 범위 내의 모든 소수를 찾는 코드를 이중 for문으로 구현할 수 있다.

 

이 때 range 범위 작성에 헷갈리지 않도록 주의하자.

 

• 'if check == True: 조건문'은 'if check : 조건문'과 동일하다

 

# ch.4
# ch.3에서 효율성 향상_'에라토스테네스의 체' 적용

a = int(input())
li = []

for n in range(2,a+1):
    check = True
    for i in range(2, int(n**0.5)+1):
        if n%i == 0:
            check = False
    if check:
        li.append(n)

print(li)


# 5
# [2, 3, 5]
# time :  0.31794142723083496

코드 스터디를 진행하며 접했던, '에라스토테네스의 체'를 적용하였다.

 

for문이 2 ~ n 범위일 때보다 2 ~ n**0.5일 때 계산 과정이 줄어든다.

 

이처럼 소수 구현을 할 때 에라스토테네스의 체를 적극적으로 활용하면 좋은 코드 작성에 도움이 될 것이다.

 

 

2021.12.04 - [Algorithm Study] - [백준 파이썬] 에라토스테네스의 체

[백준 파이썬] 에라토스테네스의 체