백준 1978 소수찾기

1978번: 소수 찾기Baekjoon Online Judge

Solution 1.

• 17812 kb / 216 ms

• 풀이

  • 역시 에라토스테네스의 체를 이용해서 풀었다.

  • 초기에 입력값을 배열로 저장하려는 시도를 했지만, 풀이를 진행하면서 굳이 그럴 필요가 없다는 것을 알게 되었고, 이내 입력을 받자마자 바로 소수 배열 내 존재여부를 체크하는 방향으로 코드를 수정하였다.

package practice.algorithm.math;

import java.util.Scanner;

public class Bj1978_1 {

    public static boolean[] isPrime = new boolean[1001];

    public static void main(String[] args) {

        isPrime();

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        int count = 0;
        while(n > 0) {
            if (!isPrime[sc.nextInt()]) {
                count++;
            }
            n--;
        }

        System.out.println(count);
    }

    private static void isPrime() {
        //true : 소수 아님, false : 소수임
        isPrime[0] = isPrime[1] = true;

        for (int i = 0; i < Math.sqrt(isPrime.length); i++) {
            if (!isPrime[i]) {
                for (int j = i*i; j < isPrime.length; j += i) {
                    isPrime[j] = true;
                }
            }
        }
    }


}

Solution 2.

• 17748 kb / 220 ms

• 제곱근을 이용한 기본 판별법

package practice.algorithm.math;

import java.util.Scanner;

public class Bj1978_2 {
    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++) {
            boolean isPrime = true;

            int num = sc.nextInt();

            if (num == 1) continue;

            for (int j = 2; j <= Math.sqrt(num); j++) {
                if (num % j == 0) {
                    isPrime = false;
                    break;
                }
            }

            if (isPrime) {
                count++;
            }
        }

        System.out.println(count);
    }
}