[Baekjoon] 1929 소수 구하기(에라토스테네스의 체)(파이썬/자바스크립트/NodeJS)

이번 문제는 아래 링크에서 풀어볼 수 있습니다.

1929번: 소수 구하기

---

문제

M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.

출력

한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.

예제 입력 1

3 16

예제 출력 1

3
5
7
11
13

---

정답 코드

답안 1
파이썬 Ver.

import sys

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


def answer1(m, n):
    print("answer1")

    def isPrime(num):
        if num == 1:
            return False
        else:
            for i in range(2, int(num**0.5) + 1):
                if num % i == 0:
                    return False
            return True

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


answer1(m, n)

NodeJS/자바스크립트 Ver.

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
let input = fs
    .readFileSync(filePath)
    .toString()
    .trim()
    .split(' ')
    .map((val) => parseInt(val));

const m = input[0];
const n = input[1];

const answer1 = (m, n) => {
    console.log('answer1');

    const isPrime = (num) => {
        if (num === 1) return false;

        for (let i = 2; i <= Math.sqrt(num); i++) {
            if (num % i === 0) return false;
        }

        return true;
    };

    for (let i = m; i <= n; i++) {
        if (isPrime(i)) console.log(i);
    }
};

answer1(m, n);

 

답안 2
파이썬 Ver.

import sys
import math

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


def answer2(m, n):
    print("answer2")

    arr = [True for _ in range(n + 1)]
    arr[0], arr[1] = False, False

    for i in range(2, int(math.sqrt(n)) + 1):
        if arr[i]:
            for j in range(i * 2, n + 1, i):
                arr[j] = False

    for i in range(m, n + 1):
        if arr[i]:
            print(i)


answer2(m, n)

NodeJS/자바스크립트 Ver.

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
let input = fs
    .readFileSync(filePath)
    .toString()
    .trim()
    .split(' ')
    .map((val) => parseInt(val));

const m = input[0];
const n = input[1];

const answer2 = (m, n) => {
    console.log('answer2');

    let arr = Array(n + 1).fill(true);

    arr[0] = false;
    arr[1] = false;

    for (let i = 2; i <= Math.sqrt(n); i++) {
        if (arr[i]) {
            // for (let j = i * 2; j <= n; j += i) {
            //     arr[j] = false;
            // }
            let j = 2;
            while (i * j <= n) {
                arr[i * j] = false;
                j++;
            }
        }
    }

    for (let i = m; i <= n; i++) {
        if (arr[i]) console.log(i);
    }
};

answer2(m, n);

답안 3
파이썬 Ver.

import sys

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


def answer3(m, n):
    print("answer3")

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

        for j in range(2, int(i**0.5) + 1):
            if i % j == 0:
                break
        else:
            print(i)


answer3(m, n)

NodeJS/자바스크립트 Ver.

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
let input = fs
    .readFileSync(filePath)
    .toString()
    .trim()
    .split(' ')
    .map((val) => parseInt(val));

const m = input[0];
const n = input[1];

const answer3 = (m, n) => {
    console.log('answer3');

    for (let i = m; i <= n; i++) {
        if (i === 1) continue;

        let isPrime = true;
        for (let j = 2; j <= Math.sqrt(i); j++) {
            if (i % j === 0) {
                isPrime = false;
            }
        }

        if (isPrime) console.log(i);
    }
};

answer3(m, n);

 

---

문제 풀이

 이전 글에서처럼 일반적인 소수 판별 코드를 작성하면 시간초과가 뜬다. n이하의 수에서 소수를 판별해내는 에라토스테네스의 체 알고리즘을 사용하면 이 문제를 해결할 수 있다.

 답안 1을 기준으로 설명하겠다. 우선 m부터 n + 1까지의 수를 for 반복문을 통해 계산하면서 isPrime이라는 소수 판별 함수에 해당 숫자를 매개변수로 전달한다. isPrime 함수 내에서는 매개변수로 전달된 num이 1이라면 당연히 소수가 아니기 때문에 continue로 다음 반복문으로 작업을 넘긴다. 실질적인 검증 작업은 2부터인데 이때 int(num**0.5) + 1의 꼴로 전달된 매개변수의 제곱근까지만 탐색을 한다는 점에 유의하자. 이는 특정 숫자 이하의 숫자가 소수임을 판별할 때 굳이 전체 숫자를 탐색할 필요가 없어서이다. 숫자의 약수는 대칭으로 이루어져 있다. 예를 들어 12의 약수는 1, 2, 3, 4, 6, 12이고 1 * 12, 12 * 1 과 같이 대칭임을 볼 수 있다. 따라서 제곱근보다 같거나 작은 수까지만 확인하면 된다. 이렇게 매개변수 num과 제곱근 보다 작은 숫자 i를 나눠 나머지가 0이라면 1과 자신 이외에 나눠 떨어지는 숫자가 존재하여 소수가 아니므로 False를 반환하고 위 과정을 모두 통과하면 True를 반환하여 정답을 print 메서드로 출력한다.

---

함께 보기

https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전

https://sso-feeling.tistory.com/387

[백준] 1929 소수 구하기 파이썬 풀이 (기본수학2)

https://mail-study.tistory.com/4

[백준] 1929번 : 소수 구하기 (python 파이썬) [에라토스테네스의 체]

https://coarmok.tistory.com/entry/%ED%8C%8C%EC%9D%B4%EC%8D%ACpython-%EB%B0%B1%EC%A4%80-1929%EB%B2%88-%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98-%EC%B2%B4

[파이썬python] 백준 1929번 - 에라토스테네스의 체

https://deokkk9.tistory.com/17

[python 파이썬] 백준 1929번: 소수 구하기

https://velog.io/@yj_lee/%EB%B0%B1%EC%A4%80-1929%EB%B2%88-%EC%86%8C%EC%88%98-%EA%B5%AC%ED%95%98%EA%B8%B0-%ED%8C%8C%EC%9D%B4%EC%8D%AC

[백준] 1929번 : 소수 구하기 (파이썬)