[백준] 1929번 : 소수 구하기 - python

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

 

---

• 문제

---

• 설계하기(접근방법) 

1. m, n을 입력받는다

2. 기존의 방식으로 소수를 구하면 시간을  초과할 것이다.

방법 1. 검사할 때 n의 루트까지만 검사한다

방법 2. m ~ n을 1 ~ n 전부 순회하며 소수인지 아닌지 판별하면 낭비일 것이다. n의 루트까지의 소수 리스트를

미리 만들면 소수의 개수 만큼만 순회하면 된다.

 

 

 

---

• 코드(출력)

m, n = map(int, input().split())  # 10 40

prime_end = int(n ** (1/2))  # 소수 검사할 때, n의 루트까지만 순회하면 된다 # 6


def find_primenumber(num): # 소수를 구하는 메서드
    if (num == 1):
        return 0
    for i in range(2, num):
        if (num % i == 0):
            return 0
    return num


primenum_list = [] # 소수 리스트

for i in range(1, prime_end + 1):  # 1 ~ 6
    if (find_primenumber(i) > 0): # 소수가 아니면 0 반환, 소수라면 num 반환
        primenum_list.append(i)


for j in range(m, n + 1):  # 10 40
    if (j == 1): # 1은 소수가 아님
        continue
    cnt = len(primenum_list) # 리스트의 원소 만큼 cnt선언
    for i in primenum_list:  # [2, 3 ,5]
        if (j % i == 0): # 나누어 떨어진다면
            if (j == i): # 소수 자기 자신을 나누는 경우 제외
                print(j) # 소수 출력
            else:
                break # 나누어 떨어진다면 = 소수가 아님
        else:
            cnt -= 1 # 나누어 떨어지지 않았다면 primnum_list의 첫번째 검사를 통과한 것
    if (cnt == 0): # 리스트 원소의 개수만큼 순회해서 모든 검사를 통과했다면 소수이다
        print(j)

---

• 얻어갈 부분

1. 내가 사용했던 방법이 에라토스테네스의 체(소수 구하기) 문제인걸 알게 되었다.

다른 사람들의 코드를 보니 True, False 리스트를 만들어 소수를 걸렀다. 다음에는 이 코드도 활용해보자

2. 시간 초과를 방지하기 위해서는 절대로 막코딩해서는 안된다. 미리 방법을 생각하고 코드를 설계해야 한다.