[1929번] 소수 구하기 / python3 (다시 만난 소수)

문제 링크: https://www.acmicpc.net/problem/1929

1929번: 소수 구하기

블로그 시작하기 전 소수 찾기 문제를 몇 번 풀었던 적이 있었는데, 시간이 흐른 지금!

다시 잘 풀 수 있을까???

---

❌ 1~2차시도 실패

1차시도(소수 함수이용) 2차시도(while 없애고 not 소수 함수 이용)

열심히 def로  식을 써봤는데도 시간초과가 나왔다......

m, n = map(int,input().split())
 
# 나머지가 0인것이 없어야함
 
#1. 소수 찾기 함수
#2. 반복문 통해 m~n사이 숫자들을 소수찾기 함수를 돌려서 출력
 
def sosu(x):
    i=2 #나누는 값 i (2부터 나누기 시작)
    while i != x: #나누는 값이 x값과 같으면 반복문 중단
        if x%i==0: #나머지가 0 (소수 아님)
            break
        else: #나머지가 0아님 (소수 가능성)
            if i==x-1:  #가장 마지막까지 돌렸는데도 나머지 0이 없는 경우
                return print(x)
            else:   #나누는 수에 증가시킬수 있는 경우
                i+=1
            
    return         
 
for i in range(m,n+1):
    sosu(i)

 

이전에는 count와 sum 문제였여서

하나하나 출력하는 이번 문제와는 다른 유형이었다... ㅠㅠ 

 

알고리즘 분류가 어떤 건가 싶어서 살펴봤더니..

에라토스테네스의 체???

 

이건 또 뭔가여 ????? 샛길 공부의 시작인가 ㅋㅋㅋㅋㅋ

---

❓ 정답은 ?? 2가지 방법

방법1 )약수의 성질을 이용한 업그레이드 소수알고리즘

방법2 )에라토스테네스의 체

  - 2가지 방법의 알고리즘 기본 공식은 여기에 정리해 뒀어요! 

  👉👉https://coding-nurse.tistory.com/44?category=975208

[샛길공부] 소수판별,에라토스테네스의 체(feat. 이코테 유튜브강의)

---

방법1 )약수의 성질을 이용한 업그레이드 소수알고리즘

#업그레이드 소수 알고리즘
 
def sosu_upgrade(x):    #약수의 성질을 이용한 개선 소수알고리즘
    if x==1:
        return False    #논외 대상이니 False
    else:
        for i in range(2,int(x**(1/2))+1):   #범위는 2부터~x제곱근까지
            if x%i==0:  
                return False    #나눠 떨어지니까 False
        return True #다른 것들은 True
                   
m, n = map(int,input().split())
 
for i in range(m,n+1):
    if sosu_upgrade(i):
        print(i)

방법2 )에라토스테네스의 체

import math
m,n= map(int,input().split())
 
#먼저, 큰 수인 n까지 소수들을 찾고 
#나중에 m부터 n까지 범위 설정해서 답 출력하기
 
array=[True for _ in range(n+1)]
array[1]=False    # m이 1일수도 있으니 미리False 처리
 
for i in range(2,int(math.sqrt(n)+1)):
    if array[i] == True:
        j=2
        while i*j<=n:
            array[i*j] = False
            j+=1
 
for k in range(m,n+1): #범위 m부터~(n+1)미만까지
    if array[k]:
        print(k)

---

💯 풀이 과정

<방법 2>에라토스테네스의 체가 코드를 사용할 때 생각할 게 많긴하지만,

그래도 <방법1> 약수의 성질 이용한 소수알고리즘보다 시간 약5배 절약, 코드길이 약2배 절약한 것을 볼 수 있다.

 

방법1은 기본 공식에서 1을 미리 false로 처리해주는 것처럼

방법2에서도 미리 처리를 꼭 해줘야 한다!

---

😎오늘의 한줄평: 나중에도 잊지않고 잘 쓸 수 있는 내가 되길!