소수구하기 with Python

---

📖 문제설명

• 문제 링크 : https://www.acmicpc.net/problem/1929
• M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.
• 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다.
• 제약 사항
  • (1 ≤ M≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.

💡 문제 요구사항 분석

• n 이상 m 이하를 반복문으로 순회를 합니다.
• 반복문의 변수를 i 를 할당합니다.
• 2 이상부터 i 미만까지 반복문을 순회를 합니다.
• 순회하면서 i 의 값이 나누어 떨어지는 수가 있다는 i 는 소수가 아님을 증명할 수 있습니다.
• i 의 값에 나누어 떨어지는 수가 없다면 answer 배열에 넣어줍니다.
• 반복문이 종료되었다면 answer 배열을 출력해 줍니다.

💡 코드풀이

1. import sys

import sys

• 빠른 입출력을 위해 sys 라이브러리를 사용합니다.
  
  

2. n, m 변수 할당

n, m = map(int, sys.stdin.readline().split())

• 입력받은 두 수를 n 과 m변수에 할당합니다.
  
  

3. answer 배열

answer = []

• answer 배열 초기화 해줍니다.
• answer 는 소수인 수를 담아줄 배열입니다.
  
  

4. n 이상 m 이하 반복문

for i in range(n, m + 1):

• n 이상 m이하의 소수를 찾기 위한 반복문입니다.
  
  

5. Flag

flag = True

• 소수인지 여부를 판별할 flag 변수를 True 로 초기화 해줍니다.

6. 소수여부 판별 반복문

for j in range(2, i):
    if i % j == 0:
        flag = False
        break

• 2부터 i 미만까지 반복문을 실행합니다.
• i % j == 0 을 통해 나누어 떨어지는 수가 있는지 판별합니다.
• 나누어 떨어지는 수가 있다면 flag = False 로 초기화해주고 반복문을 종료합니다.
• 나누어 떨어지는 수가 없다면 2부터 i까지 반복문이 돌아갈것입니다.

7. flag를 통해 소수 여부 판별

if flag:
     answer.append(i)

• 만약 flag 가 True 면 answer 배열에 i 를 넣어줍니다.
• 만약 flag 가 False 소수가 아니기 때문에 if 문을 수행하지 않습니다.
  
  
  

8. 정답 출력

for i in answer:
    print(i)

• answer 배열을 순회하면서 정답을 출력해줍니다.
  
  
  
  

전체 코드

---

import sys

n, m = map(int, sys.stdin.readline().split())
answer = []
for i in range(n, m + 1):
    flag = True
    for j in range(2, i):
        if i % j == 0:
            flag = False
            break

    if flag:
        answer.append(i)

for i in answer:
    print(i)

🚨 문제점

• 제약사항에 M에 크기가 1,000,000 이상 올 수 있기 때문에 해당 코드를 이용하여 풀 수 없습니다 !!
  - (1 ≤ M≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.
  
  
  
  
  
  
  💡 개선점

• 에라토스테네스의 체를 이용하면 시간복잡도를 해결할 수 있습니다.

• 구하고자 하는 수까지 배열을 초기화 해줍니다.
• 각 배열요소에 index에 맞춰 배열을 생성해줍니다.

• 2는 소수이므로 오른쪽에 Pime numbers 배열에 2를 추가해줍니다.

• 2의 배수는 소수가 아니므로 2의 배수를 반복문으로 순회하면서 제외시켜줍니다.

• 그 다음 3의 수는 소수이므로 Prime numbers 배열에 추가해줍니다.

• 이전 수행과 마찬가지로 3의 배수는 소수가 아니기 때문에 3의 배수는 제외시켜줍니다.

• 그다음 4를 기점으로 순회를 하여야 하지만 4는 이미 제외된 수 이기 때문에 Prime numbers 배열에 할당해주지 않고 다음 수로 넘어가게 됩니다.

👌 전체 로직

---

• 이러한 과정을 반복하여 소수를 구해주면 시간복잡도를 해결할 수 있습니다.

💡 코드 구현

1. 소수 배열 선언

arr = [1 for i in range(m + 1)]

• 소수 여부를 판별할 배열을 선언해줍니다.

2. 소수를 담을 배열 선언

primeNumbers = []

• primeNumbers 배열은 n 이상 m 이하의 소수를 담을 배열입니다.

3. 반복문

for i in range(2, m + 1):

• 2 부터 m까지 반복문을 수행해줍니다.

4. 예외처리

if arr[i] != 0:
        if n <= i <= m:
            primeNumbers.append(i)

• arr[i] 배열이 0이 아니라면 소수입니다.
• 하지만 n 부터 m 까지의 소수를 primeNumbers 배열에 담아야 하기 때문에 if n <= i <= m 를 통해 예외처리를 해줍니다.

5. i 의 배수 소수 제외

for j in range(i, m + 1, i):
    arr[j] = 0

• i 부터 m 까지 i 의 배수를 0으로 초기화하여 소수에서 제외시킵니다.

6. 정답출력

for i in primeNumbers:
    print(i)

• n 부터 m 까지의 소수를 담아놨던 primeNumbers 배열을 반복문을 통해 출력해줍니다.

💡 전체 코드

import sys

n, m = map(int, sys.stdin.readline().split())

arr = [1 for i in range(m + 1)]
primeNumbers = []

for i in range(2, m + 1):
    if arr[i] != 0:
        if n <= i <= m:
            primeNumbers.append(i)
    for j in range(i, m + 1, i):
        arr[j] = 0

for i in primeNumbers:
    print(i)

💡 채첨

• 에라토스테네스의 체 알고리즘의 시간 복잡도는  O(n * log(log n)) 이기에 큰 수도 무리없이 실행시킬 수 있습니다.