[네이버클라우드 캠프/3주차] 소수 출력하기

 

소수를 구하는 문제를 풀 때.. 정말 힘들었습니다.

 

앞서 풀었던 과제 중

'사용자에게 10개의 정수를 입력받고, 소수의 개수를 출력하세요. (단, 입력 값은 2`30 제한)'와 같이

입력받는 수가 제한되어 있을 경우에는 비교적 수월하게 풀이했습니다.

 

입력받는 수의 범위가 제한되어 있을 경우와 제한되지 않을 경우로 나누어 풀이를 설명하도록 하겠습니다.

 

❓문제 : 사용자에게 10개의 정수를 입력받고, 소수의 개수를 출력하세요. (단, 입력 값은 2`30 제한)

1. 소수와 소수가 아닌 수의 특징을 찾았습니다.

<소수>
2 3 5 7 
11 13 17 19
23 29
→ 공통점 : 홀수 (9, 15, 21, 25, 27 제외 : 3이나 5의 배수)
                짝수 (2)

<소수가 아닌 수>
4 6 8 9 10
12 14 15 16 18 20
21 22 24 25 26 27 28 30
→ 공통점 : 짝수 (2 제외)
                홀수 (9, 15, 21, 25, 27 : 3이나 5의 배수)

 

2. 최종 소스코드

public class Main {
	public static void main(String[] args) {
		int num[] = new int[10];
		int count = 0;
		
		Scanner sc = new Scanner(System.in);
		for(int i = 0; i < 10; i++) {
			System.out.printf("%d번째 정수 입력 (2`30 제한) > ", i + 1);
			num[i] = sc.nextInt(); sc.nextLine();
		}
		
		for(int i = 0; i < num.length; i++) {
			if(num[i]%2 == 0 && num[i] != 2) {
				// 어떤 동작도 X
			} else if((num[i] != 3 && num[i]%3 == 0) || (num[i] != 5 && num[i]%5 == 0)) {
				// 어떤 동작도 X
			} else {
				count++;
			}
		}
		System.out.println("소수의 개수 : " + count);
	}
}

 

1에서 찾은 소수의 특징을 통해 위의 소스코드를 작성했습니다.

(1) 2의 배수이지만 (짝수지만) 2가 아니라면 소수가 아닌 수이므로 어떤 동작도 실행하지 않습니다.

(2) 3의 배수이지만 3이 아니라면, 5의 배수지만 5가 아니라면 소수가 아닌 수이므로 어떤 동작도 실행하지 않습니다.

(3) 그 외의 경우에는 소수이므로 소수의 개수 count가 + 1가 실행됩니다.

 

자.. 그럼 이제 (드디어) 입력 받은 정수까지의 모든 소수를 출력하는 소스코드를 작성해 보도록 합시다.

 

❓문제 : 입력 받은 정수까지의 모든 소수를 출력하세요.

1. 생각 정리

소수란?
1과 자기자신만을 약수로 가지는 수

<소수>
2 3 5 7 
11 13 17 19
23 29
31 37
...

<소수가 아닌 수>
4 6 8 9 10
12 14 15 16 18 20
21 22 24 25 26 27 28 30
32 33 34 35 36 38 39 40
42 44 45 46 48 49 
...

→ 배수의 개념과 활용하기에는 경우의 수가 너무 많다.

RESET

소수란?
자기자신 미만 두 수의 곱으로 만들 수 없는 수

→ 중첩 for문으로 모두 확인해 볼까?

 

2. 사용자에 정수 입력받는 소스코드 작성

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.print("정수 입력 > "); int n = sc.nextInt();
    }
}

 

3. 소수인지 아닌지 확인하기 위한 for문 작성

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.print("정수 입력 > "); int n = sc.nextInt();
        
        for(int i = 2; i <= n; i++) {
            // 소수는 0, 소수가 아닌 수는 0 초과
            int count = 0;
            
            // 소수가 아닌 수
            for(int j = 2; j <= i; j++) {
                if(i % j == 0 && i != j) {
                    count++;
                    break;
                }
            }
            
            // 소수
            if(count == 0) {
                System.out.print(i + " ");
            }
        }
    }
}

 

소수가 아닌 수는 자신 미만의 수로 나눠 떨어진다면 count가 1이 되어, 안의 for문을 나가도록 하였습니다.

(count가 1 이상이라면 이미 소수가 아니라는 것을 확인했으므로 break로 for문 탈출)

소수는 자신 미만의 수로 나눠 떨어지지 않는다면, count가 0이므로 소수로 판단하여 출력하도록 작성했습니다.

 

🌱 마무리

첫 번째 문제를 풀이할 때 소수의 개념에 어렵게(?) 접근하니,

두 번째 문제를 풀이할 때도 비슷한 방향으로만 사고했습니다.

사고를 전환시켜 새로운 방향으로 방법을 모색하는 것에 대해 잘 깨우쳐야 할 것 같습니다.

 

더불어, 위 문제와 같이 count가 이미 1이라는 것은

소수가 아니라는 것이므로 더이상의 확인은 불필요하다는 것도 알게 되었고

이를 다른 문제를 풀 때에도 적용시켜 풀 수 있도록 더 연습해야 할 것 같습니다. 가보자고 ~ 🌱