[Java] 백준 #1978 (기본 수학2)

📍 출처

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

📝 문제

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

⌨️ 입력

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

🖨 출력

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

⌨️ 예제 입력

4
1 3 5 7

🖨 예제 출력

3

📚 내가 제출한 코드

import java.util.Scanner;

public class Main {

	static Scanner sc = new Scanner(System.in);

	public static void main(String[] args) {
		
		int testCase = sc.nextInt();
		int count = 0;

		for(int i = 0 ; i < testCase ; i++){
			if(check()){
				count++;
			}
		}
		System.out.print(count);
	}

	public static boolean check(){
		int num = sc.nextInt();

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

		if(num == 1){return false;}

		return true;
	}
}

✏️ 내가 제출한 코드에 대한 설명

소수인지 아닌지 판별하기 위해선 2부터 자기자신 -1 까지 나누어지는 수가 있나 확인해봐야한다. 하지만 그렇게 하면 좋은 성능을 발휘하지 못한다. * 빅오가 n이 됨

그래서 나는 아래와 같은 개념을 적용해 문제를 풀었다.

Number 을 A × B 의 합성수 (Number = A × B) 라고 볼 때 아래와 같이 부등식을 세울 수 있다.

⇨ ( 1 ≤ A, B < Number )

여기서 만약 A 와 B 가 Number 의 제곱근보다 커지면 위 부등식에 모순이 생긴다.

A, B > sqrt( Number )

↳ A × B > Number

위 식은 결국 A × B = Number 라는 식과 모순이므로 다음과 같은 결론을 내릴 수 있다.

∴ 합성수 Number = A × B 에서 A 와 B 중 적어도 하나는 Number 의 제곱근보다 작거나 같다.

​

쉽게 설명하면 17의 소수를 구할 때 17의 제곱근까지 나눠지는 수가 없으면 그 이후도 없을거란 얘기이다.

이러한 개념을 바탕으로 코드를 짜 true를 return 하면 count +1 이 되도록하였다.