[JAVA] 1978번 - 소수 찾기

[JAVA] 1978번 - 소수 찾기

출처 - https://www.acmicpc.net/problem/1978

문제

주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오.

입력

첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다.

출력

주어진 수들 중 소수의 개수를 출력한다.

예제 입력 1 4 1 3 5 7

예제 출력 1 3

< 소스 코드 >

import java.io.*; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); int n = Integer.parseInt(br.readLine()); int[] arr = new int[n]; int primeNumber = 0; // 소수의 개수 StringTokenizer st = new StringTokenizer(br.readLine()); for(int i=0; i

이 문제는 숫자를 입력받아 소수를 판별하여 개수를 출력하는 문제 이다.

소수라는 것은 어떤 자연수가 존재할 때, 1하고 자기자신만 나누어떨어지는 수이다.

사실 대학교 전공과목인 암호학을 공부할 때 가장 중요한 부분이기도 하다.

그중에서 소수 판별법이 여러 가지 존재했다.

기억하기로는 페르마, 밀러-라빈, 에라토스테네스의 체 등 많았던 것 같다.

가장 간단한 것은 자연수의 약수를 구할 때, 1부터 N-1까지의 범위에서 존재하기 때문에

1을 제외하고 N-1까지 나누어 떨어지는지 계속 반복하는 것이다.

범위 안에서 나누어 떨어지는 수가 있다면, 소수가 아님이 판별된다.

하지만 효율이 떨어지기 때문에 자연수의 제곱근을 구하고 그 범위안에서 비교 하는 것이다.

예를 들어, 45가 소수인지 아닌지 궁금하다면, 45의 제곱근을 구한다.

45의 제곱근은 6.xxx가 나올 것이며, 2 ≤ x ≤ 6 범위 내에서 45가 나누어 떨어지는 수가 있는지

구할 수 있다. 나누어 떨어진다면 그 수는 소수가 아닌 것이다.

위의 방법보다는 범위가 좁아 훨씬 효율적이다.

사실 이것보다 효율적인 알고리즘은 존재하지만 아직 구현하기엔 미숙하다.

수의 제곱근을 구하기 위해 중요한 것은 제곱근을 구하는 함수이며, 그 함수는

Math.sqrt()이며 이를 이용하여 이 문제를 해결한다.

from http://puzzle-moon.tistory.com/80 by ccl(A) rewrite - 2021-12-28 13:02:04