[백준] 1978번: 소수 찾기 [JAVA]

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

문제

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

입력

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

출력

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

---

알고리즘

소수란 1과 자기 자신만을 약수로 갖고 있는 수를 말합니다.(ex. 2, 3, 5, 7, 11, ...)

이번 문제는 입력된 숫자들 중에서 소수의 개수를 출력하는 문제입니다.

 

소수를 구하는 방법으로는

1. 단순하게 2부터 입력된 숫자 바로 전까지의 수로 나눠서 나머지가 0인지를 확인하는 방법

 

2. 입력된 숫자의 절반까지만 나머지가 0인지를 확인하는 방법

 -이 방법은 만약 약수가 있다면 절반에서 무조건 나머지가 0이 되는 수가 나오기 때문에 가능한 방법입니다.

 

3. 입력된 숫자가 num이라고 할 때, √num의 범위까지만 나머지를 확인하는 방법(에라토스테네스의 체)

 - 이 방법은 숫자 100을 예시로 보면 

     1, 2, 4, 5, 10, 20, 25, 50, 100 을 각각 짝지어본다면

   1:100, 2:50, 4:25, 5:20, 10:10 으로 √100이면 10이 나오고 해당값이 중간값이 되는 것을 확인하실 수 있습니다.

   다른 숫자로 70을 보면

     1, 2, 5, 7, 10, 14, 35, 70

   1:70, 2:35, 5:14, 7:10 으로 √70은 8.36xx.. 이므로 중간값인 7의 근사치로 나오게 됩니다.

  이것을 이용하여 좀 더 효율적으로 소수를 판별하는 방식입니다.

 

---

코드

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 N = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());
		int num, count = 0;
		for(int i = 0; i < N; i++) {
			num = Integer.parseInt(st.nextToken());
			if(Prime(num)) {
				count++;
			}
		}
		System.out.println(count);
	}
    
	static boolean Prime(int num) {
//     		1은 소수가 아니다.
		if(num < 2)
			return false;
//		1. 시간복잡도 O(N) N번 조회
//		for(int i = 2; i < num; i++) {
//			if(num%i == 0) {
//				return false;
//			}
//		}
//		2. 시간복잡도 O(N) N/2번 조회
//		for(int i = 2; i <= num/2; i++) {
//			if(num%i == 0) {
//				return false;
//			}
//		}
//		3. 시간복잡도 O(√N) √N번 조회
		for(int i = 2; i*i <= num; i++) {
			if(num%i == 0) {
				return false;
			}
		}
		return true;
	}
}

---

 

이 글의 알고리즘이나 코드에서 지적할만한 부분은 댓글에 남겨주시면 저에게 많은 힘이 됩니다!