Math.sqrt(n) 함수를 활용해 정수 N이 소수인지 판별하는 함수

※ 소수는 1과 자기 스스로만이 약수이다.

정수 N의 약수 a,b에 대해 N = ab가 성립된다.

여기서 a <= b 라 가정을 하면, 1 <= a <= √N, √N <= b <= N 이 성립된다.

정수 N이 소수가 아니라면, 2와 √N 사이에 약수가 존재한다.

import java.io.*;
import java.lang.*;
import java.util.*;


public class Main {
	public static final Scanner scanner = new Scanner(System.in);

	/**
    * 주어진 숫자가 소수인지 판별하는 함수 
    *
    * @param N 
    * @return true   소수라면 
    * @return false  소수가 아니라면
    */
	public static boolean isPrime(int N){ //반환값이 논리형
		
		if( N == 1) return false;
		if( N == 2) return true;
		else if(N%2 == 0) return false; //N이 2로 나눈 나머지가 0이면 == 짝수면 거짓
		
		int count = 0; //1,N 미리 고려
		for(int i = 3; i <= Math.sqrt(N); i += 2){ //math.srqt(N) = 정수 N이 어떤 정수 x의 제곱인지 판단하는 함수
			// i := [2, sqrt(N)] 사이의 모든 정수
			if( N % i == 0 ){ //N이 i로 나누어 떨어지면, 소수가 아님
				count +=1; //count를 1 증가
				break; //소수가 아님이 판별되었으니 반복문을 빠져나옴
			}
		}
		
		//count := [2, sqrt(N)]의 모든 약수의 갯수
		return count == 0; //count가 0이라면(범위 내에서 N의 약수가 발견되지 않은 경우) 소수(진실), 아니면 소수가 아님(거짓)
	}

	public static void testCase(int caseIndex)
	{
		int n = scanner.nextInt();
		boolean result = isPrime(n);

		System.out.printf("Case #%d\n", caseIndex);
		if(result)
		{
			System.out.println("YES");
		}else{
			System.out.println("NO");
		}
	}

	public static void main(String[] args) throws Exception {
		int caseSize = scanner.nextInt();

		for (int caseIndex = 1; caseIndex <= caseSize; caseIndex += 1) {
			testCase(caseIndex);
		}
	}

}

 

10주 완성 알고리즘 코딩테스트 - goorm edu에서 들으실 수 있는 내용입니다.