ShaShaKa Dev Note

소수 찾기

23 June 2019

문제 : https://www.acmicpc.net/problem/1978

이번은 소수의 갯수를 구하는 문제를 풀어보도록 하겠습니다.

import java.util.Scanner;

public class Main {

    private static int[] primeNumbers = new int[1001];

    public static void main(String args[]) {

        primeNumbers[1] = 1;
        for (int i = 2; i < primeNumbers.length - 1; i++) {
            int k = 2;
            while (true) {
                if (k * i > primeNumbers.length - 1) {
                    break;
                }
                primeNumbers[k * i]++;
                k++;
            }
        }

        Scanner sc = new Scanner(System.in);

        int count = 0;
        int size = sc.nextInt();
        for (int i = 0; i < size; i++) {
            int val = sc.nextInt();
            if (primeNumbers[val] == 0) {
                count++;
            }
        }

        System.out.println(count);
    }
}

이번 문제는 미리 범위 내의 소수를 구한 다음 들어오는 값에 대응하는지 판별하여 출력해주도록 합니다.
소수는 1과 자신을 제외한 어떤 값으로도 나누어지지 않는 값입니다. 따라서, 2 이상의 값부터 2 이상을 곱하여 나오는 수를 모두 제외해주면 됩니다.
2인 경우, 4,6,8,10... 3인 경우, 6,9,12..., 90인 경우, 180, 270 등으로 곱으로 나오는 값을 모두 지워주도록 합니다.
이후, 들어온 값과 구해놓은 소수를 비교하여 count를 return 해주도록 합니다.