[백준 / 실버5] 2581 : 소수 (JAVA)

문제

---

풀이 방법

• 2 이상 N 미만의 수 중에 나누어 떨어지는 수가 존재하지 않을 경우 소수로 판별
  • 시간 복잡도 : O(N²)
• 에라토스테네스의 체 알고리즘
  • 시간 복잡도 : O(Nlog(log N)) 
  • link

코드

👇🏻 기본적인 방법

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));
        int M = Integer.parseInt(br.readLine());
        int N = Integer.parseInt(br.readLine());
        int sum = 0, min = 0

        for (int i = M; i <= N; i++) {
            for (int j = 2; j <= i; j++) {
                if (i == j) {
                    sum += i;
                    if (min == 0) {
                        min = i;
                    }
                }
                if (i % j == 0) {
                    break;
                }

            }
        }
        if (sum == 0) {
            System.out.println(-1);
        } else {
            System.out.printf("%d\n%d", sum, min);
        }

    }
}

👇🏻에라토스테네스의 체 알고리즘

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

public class Main {

    static boolean[] prime;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int M = Integer.parseInt(br.readLine());
        int N = Integer.parseInt(br.readLine());
        int sum2 = 0, min2 = 0;

        makePrime(N);

        for (int i = M; i <= N; i++) {
            if (prime[i] == false) {
                sum2 += i;
                if (min2 == 0) {
                    min2 = i;
                }
            }
        }
        if (sum2 == 0) {
            System.out.println(-1);
        } else {
            System.out.printf("%d\n%d\n", sum2, min2);
        }

    }

    public static void makePrime(int N) {
        prime = new boolean[N + 1];
        prime[0] = true;
        prime[1] = true;
        for (int i = 2; i < Math.sqrt(N); i++) {
            for (int j = i * i; j < prime.length; j += i) {
                prime[j] = true;
            }
        }
    }
}