1929 소수 구하기

BOJ::1929 소수 구하기

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

범위 내 소수만 출력하는 문제.

에라토스테네스의 체를 사용하지 않으면 아마 시간초과 날 것 같다.

<JAVA>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    
    static int n,m;
    static StringBuilder sb = new StringBuilder();
    static boolean primes[]=new boolean[1000001];
    
    public static void main(String args[]) throws NumberFormatException, IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n=Integer.parseInt(st.nextToken());
        m=Integer.parseInt(st.nextToken());
        
        primes[1]=true;
        for(int i =2 ;i<=m;i++){
            for(int j = 2 ; i*j <=m; j++){
                if(!primes[i*j]){
                    primes[i*j]=true;
                }
            }
        }
        
        for(int i = n; i<=m;i++){
            if(!primes[i]){
                sb.append(i+"\n");
            }
        }
        System.out.println(sb.toString());
    }
}
 

<C++>

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;
 
vector<int> v;
int n, m;
bool primes[1000001];
 
int main() {
    cin >> n >> m;
 
    primes[1] = true;
    for (int i = 2; i <= m; i++) {
        for (int j = 2; i*j <= m; j++) {
            if (!primes[i*j]) {
                primes[i*j] = true;
            }
        }
    }
 
    for (int i = n; i <= m; i++) {
        if (!primes[i]) {
            v.push_back(i);
        }
    }
    
    for (auto& a : v) {
        cout << a << "\n";
    }
}