소수 구하기

문제

소수 구하기

풀이

에라토스테네스의 체를 이용해서 이하의 소수를 모두 구한 다음 이상 이하의 소수를 출력하면 됩니다.

코드

Python

import sys
 
input = lambda: sys.stdin.readline().rstrip()
 
m, n = map(int, input().split())
 
is_prime = [True] * (n + 1)
is_prime[1] = False
 
for i in range(2, n + 1):
    if not is_prime[i]:
        continue
    for j in range(i + i, n + 1, i):
        is_prime[j] = False
 
for i in range(m, n + 1):
    if is_prime[i]:
        print(i)

C++

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int m, n;
    cin >> m >> n;
 
    vector<bool> isPrime(n + 1, true);
    isPrime[1] = false;
    for (int i = 2; i <= n; i++) {
        if (not isPrime[i])
            continue;
        for (int j = i + i; j <= n; j += i)
            isPrime[j] = false;
    }
 
    for (int i = m; i <= n; i++) {
        if (isPrime[i])
            cout << i << '\n';
    }
 
    return 0;
}

Java

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
 
        StringTokenizer tk = new StringTokenizer(br.readLine());
        int m = Integer.parseInt(tk.nextToken()), n = Integer.parseInt(tk.nextToken());
 
        boolean isPrime[] = new boolean[n + 1];
        for (int i = 0; i <= n; i++)
            isPrime[i] = true;
 
        isPrime[1] = false;
        for (int i = 2; i <= n; i++) {
            if (!isPrime[i])
                continue;
            for (int j = i + i; j <= n; j += i)
                isPrime[j] = false;
        }
 
        for (int i = m; i <= n; i++) {
            if (isPrime[i])
                bw.write(i + "\n");
        }
 
        bw.close();
    }
}