[BOJ]1929번: 소수 구하기(java, c++)

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

1929번: 소수 구하기

 

 

방식 1. 에라토스테네스의 체 Sieve of Eratosthenes

import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
 
        Scanner sc = new Scanner(System.in);
        StringBuilder sb = new StringBuilder();
 
        int A = sc.nextInt();
        int B = sc.nextInt();
 
        boolean arrPrimeRemoved[] = new boolean[B + 1]; 
 
        for (int i = 2; i <= B; i++) {
            if (arrPrimeRemoved[i] == false) {
                if (i >= A) {
                    sb.append(i + "\n");
                }
 
                for (int j = i * 2; j <= B; j += i) {
                    arrPrimeRemoved[j] = true;
                }
            }
        }
 
        System.out.println(sb.toString());
    }
}

 

c++ 소스

//https://www.acmicpc.net/problem/1929
#include <iostream>
 
using namespace std;
 
const int MAX = 1000000;
bool isno_prime[MAX + 1];
 
void check_prime()
{
    isno_prime[0] = true;
    isno_prime[1] = true;
 
    for (int i = 2; i * i <= MAX; i++)
    {
        if (isno_prime[i] == false)
        {
            for (int j = 2; i * j <= MAX; j++)
            {
                isno_prime[i * j] = true;
            }
        }
    }
}
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    // 최대값 범위의 소수체크 미리 해놓기
    check_prime();
 
    // 입력
    int M, N;
    cin >> M >> N;
 
    // 출력
    for (int i = M; i <= N; ++i)
    {
        if (isno_prime[i] == false)
        {
            cout << i << '\n';
        }
    }
 
    return 0;
}

 

방식 2. 소수 판정하기 활용

import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
 
        Scanner sc = new Scanner(System.in);
        StringBuilder sb = new StringBuilder();
 
        int A = sc.nextInt();
        int B = sc.nextInt();
 
        boolean arrPrimeRemoved[] = new boolean[B + 1]; 
        
        arrPrimeRemoved[0] = true;
        arrPrimeRemoved[1] = true;
        
        for (int i = 2; i * i <= B; i++) {
            
            if (arrPrimeRemoved[i]) {
                continue;
            }
           
            for (int j = i * 2; j <= B; j += i) {
                arrPrimeRemoved[j] = true;
            }
        }
 
        for (int i = A; i <= B; i++) {
            if (arrPrimeRemoved[i] == false) {
                sb.append(i + "\n");
            }
        }
        System.out.println(sb.toString());
    }
}

 

 

 

방식 1. 에라토스테네스의 체 Sieve of Eratosthenes

 

 

원리

- 2부터 범위까지 모든 수를 대상으로,

- 아직 지워지지 않은 가장 작은 수는 소수

- 그 수의 배수는 소수 X --> 지운다

 

 

ㄱ. 바깥 for 문 

for (int i =2; i <= B; i++)

A ≤ k ≤ B 의 모든 소수를 구하는 것이 목표이기 때문에, 

바깥 for 문을 B까지 돌린다. 

 

ㄴ. 안쪽 for 문

for (int j = i * 2; j <= B; j += i)

j = i * i; 부터 안쪽 for 문을 시작하는게 효율적이지만, 

i = 백만인 경우 i * i는 Integer의 범위를 넘어가기 때문에 i * 2부터 시작하는게 좋다. 

 

j += i

1:  j = i * 2

2:  j = i * 2 +  i  = i * 3

3:  j = i * 2 + 2i = i * 4

...

 

j = i의 배수씩 지워나간다

 

 

 

방식 2. 소수 판정하기 활용

 

소수 판정하기를 활용해서 소수인 것으로 체크된 수들을 불러오는 방식.

 

 

 

 

방식 1이 더 빠르다!