백준[JAVA] 1929.소수 구하기 - 자바

📖 문제

📃 코드

1. Bruteforce + sqrt

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int M = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());

        for (int i = M; i <= N; i++) {
            primeNumber(i);
        }
    }

    public static void primeNumber(int number) {
        if (number < 2){
            return;
        }

        if (number == 2){
            System.out.println(number);
            return;
        }

        for (int i = 2; i <= Math.sqrt(number); i++) {
            if (number % i == 0) {
                return;
            }
        }
        System.out.println(number);
        return;
    }
}

2. 에라토스테네스의 채 + sqrt

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static boolean[] result;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int M = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());

        result = new boolean[N + 1];
        primeNumber();

        for (int i = M; i <= N; i++) {
            if(!result[i]){
                System.out.println(i);
            }
        }
    }

    // true = !prime, false = prime
    public static void primeNumber() {
        result[0] = result[1] = true;

        for (int i = 2; i <= Math.sqrt(result.length); i++) {
            if (result[i]) {
                continue;
            }
            for (int j = i * i; j < result.length; j += i) {
                result[j] = true;
            }
        }
    }
}

 

🔗 링크

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

1929번: 소수 구하기