알고리즘 (6월 19일)

1. 문제 (최대 소수값을 찾기)

---

2. 생각

입력 예시

 

1. 배열의 사이즈를 입력과 배열의 원소들을 입력받아 변수와 배열에 각각 저장한다.
2. for문을 이용하여 시작점(i)을 정의하고, 끝점(j)을 정의한다.
3. 이전까지의 값에 10을 곱한 뒤, 새로운 원소를 더해가며 원소들을 합한다.
   (▶ sum = sum*10 + storage[j] )
4. 2부터 sum까지 for문과 나머지연산자를 이용하여 해당 숫자(sum)이 소수인지 판단
   ( 소수가 아니면 isPrim = true, 소수이면 isPrim = false )
5. 만약, 해당 숫자(sum)이 소수인 동시에 max보다 크면 max값을 해당숫자로 대체한다.
6. 결과 출력

---

3. 풀이 및 코드 분석

import java.util.Scanner;

public class programming {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		
		// 사이즈 입력
		System.out.print("배열의 사이즈 입력:");
		int size = scan.nextInt();
		int[] storage = new int[size];
		
		// 원소 입력
		System.out.print("원소 입력:");
		for(int i=0; i<size; i++)
			storage[i] = scan.nextInt();
		scan.close();
		
		
		int max = 0;
		for(int i=0; i<size; i++) {
			int sum = 0;
			for(int j=i; j<size; j++) {
				sum = sum*10 + storage[j];
			
			boolean isPrim = true;
			for(int l=2; l*l<=sum&&isPrim; l++)
				if(sum%l==0)
					isPrim = false;
				
			if(sum>max&&isPrim&&sum!=1)
				max=sum;
			}
		}
		
		if(max==0) 
			System.out.println("최대 소수값은 존재하지 않습니다.");
		else
			System.out.println("1개 이상의 연속된 정수값들을 합하여 얻을 수 있는 최대 소수값:"+max);
	}
}

---

4. 메모

• 위 문제에는 한 가지 오류와 한 가지 한계점이 존재한다.
• 오류는 1을 소수로 인식한다는 점이다. 왜냐하면 소수 판별과정에서 sum = 1인 경우, l이 2부터 시작하는데, 당연하게도 2는 1보다 크기 때문에 소수 판별하는 for문이 동작하지 않기 때문이다. 따라서 sum=1은 isPrim=true 상태를 유지하면서 max값보다 큰지 판별하게 되어 1을 소수로 인식한다.
• 위 오류를 방지하기 위해서 sum = 1이 아닌 경우에만 max 값보다 큰지 판별하도록 설계
• 한계점은 int 자료형의 정수 표현 범위이다. int 자료형은 4바이트이기 때문에 -2^31 ~ 2^31까지만 표현이 가능하다. 따라서 int 자료형의 점수 표현 범위를 넘게 되면 더 이상 의미없는 숫자가 들어가기 때문에 한계점이라고 할 수 있다.
• 물론 long 자료형을 통해 범위를 넓힐 수는  있지만, long 자료형의 범위을 넘는 숫자가 들어오면 또 한 번 한계점에 도달하기 때문에 해결책이라고 보기 어렵다.