백준 1978번 소수 찾기

문제

링크 : https://www.acmicpc.net/problem/1978

나의 풀이

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        int count = 0;
        for(int i = 0; i < n; i++) {
            int t = sc.nextInt();
            if(isPrime(t)) {
                count++;
            }
        }
        System.out.println(count);
    }
    
    static boolean isPrime(int t) {
        if(t < 2) {
            return false;
        }
        for(int i = 2; i * i <= t; i++) {
            if(t % i == 0) {
                return false;
            }
        }
        return true;
    }
}

소수인지 아닌지 2부터 루트 N보다 작거나 같은 자연수로 나누어떨어지는지 여부로 판별하는 isPrime 메소드를 이용하여 입력 받은 t가 소수인 경우 count 변수를 증가시키고 마지막에 count를 출력시키게 구현하였다.

결과

1929번 소수 구하기

문제

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

나의 풀이

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();
        int n = sc.nextInt();

        boolean check[] = new boolean[n + 1];
        check[0] = true;
        check[1] = true;
        for(int i = 2; i * i <= n; i++) {
            if(check[i]) {
                continue;
            }
            for(int j = i * 2; j <= n; j += i) {
                check[j] = true;
            }
        }

        for(int i = m; i <= n; i++) {
            if(!check[i]) {
                System.out.println(i);
            }
        }
    }
}

에라토스테네스의 체를 이용하여 소수가 아닌 수를 걸러내고 m부터 n까지 for문을 돌려서 check 배열이 false인 경우에만 해당 숫자를 출력하게 구현하였다.

결과

6588번 골드바흐의 추측

문제

링크 : https://www.acmicpc.net/problem/6588

나의 풀이

import java.io.*;
import java.util.*;

public class Main {
    static final int MAX = 1000000;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        boolean check[] = new boolean[MAX + 1];
        ArrayList<Integer> prime = new ArrayList<>();
        check[0] = check[1] = true;

        for(int i = 2; i * i <= MAX; i++) {
            if(check[i]) {
                continue;
            }
            prime.add(i);
            for(int j = i * 2; j <= MAX; j += i) {
                check[j] = true;
            }
        }

        while(true) {
            int n = Integer.parseInt(br.readLine());
            if(n == 0) {
                return;
            }
            for(int i = 1; i < prime.size(); i++) {
                int p = prime.get(i);
                if(!check[n - p]) {
                    System.out.println(n + " = " + p + " + " + (n - p));
                    break;
                }
            }
        }
    }
}

스캐너 썼을 때 시간 초과 떠서 BufferedReader로 변경해주니 통과했다^^.

결과