1부터 100의 범위 안에서 가장 큰 소수를 구하는 알고리즘 풀이

2020년 11월 기출문제

 

다음은 Java 언어로 1부터 100의 범위 안에서 가장 큰 소수를 구하는 알고리즘을 구현한 것이다. 괄호 안에 들어갈 가장 적절한 답을 쓰시오.

public class Test {
	public static void main(String[] args){
    	int p = 2, n = 3;
        while(true) {
         	double t = Math.sqrt(n);
         	int m = (int) t;
         	for (int i = 2; i <= m; i++) {
        		int r = n % i;
                if (r == 0) break;
                if(i==m) p = (____);
        	}
            n++;
            if (n > 100) break;
        }
        System.out.println(p);
    }
}

 소수란? 1을 제외한 1과 자기자신으로 나눌수 있는 수를 의미한다.

 

 먼저 Math.sqrt(n)은 Jaava 기본 라이브러리(java.lang)의 Math 클래스에 포함된 제곱근을 구하는 수학 함수이다.

제곱근을 구하는 이유는 만약 n이 12라 할 때, 12의 제곱근은 약 3.46이다.
12의 약수는 1, 2, 3, 4, 6, 12 이다.
여기서 1과 12를 제외했을 때 이는 2 * 6, 3 * 4, 4 * 3, 6 * 2의 결과이다.
이들의 관계는 몫이 커지면 나누는 값이 작아지거나 나누는 값이 커지만 몫이 작아지는 반비례 관계이다. 
결국 n의 절반(제곱근)까지 향하게 되면 이후 몫과 나누는 값이 반대로 바뀌게만 되는 상황이다.

따라서 n의 제곱근까지 나누어 떨어지는지 여부를 조사하면 더 빠르게 소수판별을 할 수 있다.

 

int p = 2, n = 3;

변수 p의 초기값은 소수의 최소값, 변수 n은 소수의 최소값의 바로 다음 소수값으로 값을 지정한다.

n을 소수 최소값인 2로 정하게 되면 Math.sqrt(n) 으로 제곱근을 구할 때 1이 되어 버리는데 이는 소수의 조건에서 벗어나기 때문이다.

따로 횟수제약이 없으며 소수의 최소값이 2이기 때문에 미리 최소값을 담을 변수에 2를 저장해주고 최소값의 다음 소수값인 3부터 시작한다.

 

double t = Math.sqrt(n);
int m = (int)t;

 

n의 제곱근 값 즉, 루트 n의 값을 구한 후 실수 이므로 double타입 변수 t에 저장한다.

이후 실수 t의 값을 정수타입 int로 형변환하여 정수형 변수 m에 저장한다.

n의 제곱근 값의 소수점 이하는 생략해되어 정수값만 m에 저장된다.

 

 

for (int i = 2; i <= m; i++) {
	int r = n % i;
	if (r == 0) break;
	if(i==m) p = (____);
}
n++;

i가 2부터 시작, i가 m보다 작을때 까지 i를 1씩 증가시켜 반복문을 돌린다.

n과 i가 나누어 떨어지면 약수에 해당하므로 소수각 아니기때문에 반복문을 종료한다.

m까지로 범위를 한 이유는 소수점 이하를 생략한 n의 제곱근 값 m이 n의 정수값에서 나올 수 있는 최대 갯수이기 때문이다.

 

 

만약 n이 3이라면 m값은 1이된다.

 

m이 1이면 

3%2 즉, r값이 1로 반복문을 종료하지 않고 다음 조건문으로 넘어간다.

i의 값과 m값이 같다 라는 조건식도 성립되지 않으므로 어떠한 값을 소수 최소값 변수p에 저장하지 않고 i값을 1 증가시킨다.

반복문 자체가 실행되지 않는다.

범위의 시작값이 2 인데 m이 1이다.

i <= m;

2<=1; → false 

즉, i가 m보다 작다는 조건식 자체가 거짓이 된다.

때문에 반복문이 실행되지 않고 바로 n을 1 증가시켜 다시 while 무한루프를 실행시킨다 이때 n은 4가 된다.

 

만약 n이 4라면 m 값은 2가 된다.

m이 2이면

4%2 즉, r값이 0으로 반복문을 종료한다.

이렇게 나머지가 0으로 나누어 떨어진다면 약수에 해당하므로 소수가 아니기 때문이다. 

이후 증감연산식을 통해 n값을 증가시키고 다시 while문을 돌린다.

 

만약 n이 5라면 m값은 2가 된다.

m이 2이면

5%2 즉, r값이 1이된다. r이 0이 아니기 때문에 n값은 소수가 된다.

반복문이 종료되지 않으므로 다음 조건식인 i==m을 판별한다.

i는 현재 2이며 m도 2 즉 2=2 조건식이 참이므로 어떠한 값을 p에 저장한다.

if(i==m) p = (____);

n값 즉 5가 소수이기때문에 소수의 최소값을 담는 변수 p에 변수 n에 저장된 소수 5를 저장한다

if(i==m) p = n;

따라서 빈칸은 n이된다

 

public class Test {
	public static void main(String[] args){
    	int p = 2, n = 3;
        while(true) {
         	double t = Math.sqrt(n);
         	int m = (int) t;
         	for (int i = 2; i <= m; i++) {
        		int r = n % i;
                if (r == 0) break;
                if (i == m) p == n;
        	}
            n++;
            if (n > 100) break;
        }
        System.out.println(p);
    }
}

---

구독과 공감 혹은 댓글이 블로거에게는 큰 힘이 됩니다.