[백준] 1978 : 소수 찾기 (JAVA) - 자바 소수구하기 제곱근

 

자바 제곱근으로 소수구하기 Math.sqrt() 이용!!!!!

Math.sqrt(num) : num의 제곱근

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

예)

9의 제곱급이다. 그럼 루트 9,

i는 2, 3

루트 9는 3으로 나누어 떨어진다.

나누어떨어지니 9는 false로 리턴

 

예2)

17의 제곱근

i는 2 3 4

다 나누어 떨어지지 않으므로 소수이다!

매우간단 😉

num의 제곱근까지만 검사하는 이유!

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

1 <= A, B < Number

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

따라서 합성수 num= A x B 에서 A와 B 중 적어도 하나는 num의 제곱근보다 작거나 같다.

따라서 소수를 판별할 때 굳이 num-1 까지가 아닌 num의 제곱근까지만 검사하면 된다.

 

백준 문제 1978번이다.

소수 찾기

문제

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

입력

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

출력

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

예제 입력 1

4
1 3 5 7

예제 출력 1

3

---

 

방법1.

package Day1030;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class B1978 {

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		br.readLine(); // N 은 쓰지 않음.

		int count = 0;

		StringTokenizer st = new StringTokenizer(br.readLine(), " "); // 공백 기준으로 끊어줌

		while (st.hasMoreTokens()) { // st.hasMoreTokens() : StringTokenizer에 사용할 수 있는 토큰이 더 있는지 확인ㄴ
			boolean isPrime = true;
			int num = Integer.parseInt(st.nextToken());

			if (num == 1)
				continue; // 소수는 1을 포함 안하므로 넘어가기

			// Math.sqrt(num) : num의 제곱근
			// 2 ~ num의 제곱근까지 중 나누어 떨어지는 약수가 있는지 판별
			// num = 2 의 경우는 자연스럽게 for문을 검사하지 않게 됨
			for (int i = 2; i <= Math.sqrt(num); i++) {
				if (num % i == 0) {
					isPrime = false;
					break;
				}
			}
			// 만약 나눠떨어지지 않는다면 소수이므로 카운트
			if (isPrime) {
				count++;
			}
		}
		System.out.println(count);
	}
}

 

방법2. 메서드 호출

코드가 좀 지저분한 것 같아서 메서드 호출 방식으로 해보았다.

package Day1030;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class B1979_2 {

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		br.readLine(); // N 은 쓰지 않음.

		int count = 0;

		StringTokenizer st = new StringTokenizer(br.readLine(), " "); // 공백 기준으로 끊어줌

		while (st.hasMoreTokens()) { // st.hasMoreTokens() : StringTokenizer에 사용할 수 있는 토큰이 더 있는지 확인ㄴ
			int num = Integer.parseInt(st.nextToken());
			
			// 메서드에 num 대입해서 호출
			if (isPrime(num)) {
				count++;
			}
		}
		System.out.println(count);
	}

	// 메서드 호출 부분
	public static boolean isPrime(int num) {
		if (num == 1)
			return false;

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

		return true;
	}
}

 

위가 방법2

아래가 방법1