[알고리즘] 8. 소수 판별

소수 판별

• 1 ~ 100까지의 수 중 소수를 찾으시오.

문제 분석

• 1은 소수가 아니므로 제외

• 2는 소수이나 2의 배수 (짝수)는 제외

• 3은 소수이나 3의 배수는 제외

• 5는 소수이나 5의 배수는 제외

• ….. → 제외되지 않은 수들은 소수

• 이 방식을 에라토스테네스의 체라고 함

코드 작성 - Sampling & Moduling

package algo;

public class Pn01 {
    public static void main(String[] args) {
        // 1에서 100까지의 수 중 소수를 찾으시오.

        // 1. Sampling : 1에서 10 사이의 소수를 찾으시오.
        // 2. Hard Coding : 특징 찾기 1 - 1을 무조건 제외, 어떤 수의 배수는 전부 소수가 아님, 단 2, 3, 5, 7은 그 수와 1만을 약수로 가지므로 소수
        // 2. Hard Coding : 특징 찾기 2 - 즉, 소수랑 특정 수의 최대 공약수가 1일 경우 이는 소수 (소수의 성질 : 두 소수는 서로소)
        // 3. Moduling : 반복문, 공통화, 특징 활용

        int a = 0;
        String s = "";
        Uc f = new Uc();
        for (int i = 0; i < 10; i++) {
            a++;
            if (a == 1) System.out.println("1은 소수가 아닙니다.");
            else if (a == 2) System.out.println("2는 소수입니다.");
            else if (a == 3) System.out.println("3는 소수입니다.");
            else if (a == 5) System.out.println("5는 소수입니다.");
            else if (a == 7) System.out.println("7는 소수입니다.");
            else {
                // 3-1. 짝수가 아닌가?
                if (a % 2 == 0) System.out.println(a + "는 소수가 아닙니다.");
                    // 3-2. 3의 배수가 아닌가?
                else if (a % 3 == 0) System.out.println(a + "는 소수가 아닙니다.");
                    // 3-3. 5의 배수가 아닌가?
                else if (a % 5 == 0) System.out.println(a + "는 소수가 아닙니다.");
                    // 3-4. 7의 배수가 아닌가?
                else if (a % 7 == 0) System.out.println(a + "는 소수가 아닙니다.");
                    // 2, 3, 5, 7까지의 배수만 비교하는 이유 : 10보다 큰 소수인 11의 거듭제곱 = 121이므로 100을 넘어감, 
                    // 즉 소수 범위 내에서는 2, 3, 5, 7의 배수만 찾으면 소거법으로 다른 소수들을 전부 찾을 수 있음
                else {
                    s = f.gcd(a, 2) == 1 ? "소수입" : "소수가 아닙";
                    System.out.println(a + "은 " + s + "니다.");
                }
            }
        }
    }
}

결과

코드 완성

package algo;

public class Pn01 {
    public static void main(String[] args) {
        // 1에서 100까지의 수 중 소수를 찾으시오.

        // 1. Sampling : 1에서 10 사이의 소수를 찾으시오.
        // 2. Hard Coding : 특징 찾기 1 - 1을 무조건 제외, 어떤 수의 배수는 전부 소수가 아님, 단 2, 3, 5, 7은 그 수와 1만을 약수로 가지므로 소수
        // 2. Hard Coding : 특징 찾기 2 - 즉, 소수랑 특정 수의 최대 공약수가 1일 경우 이는 소수 (소수의 성질 : 두 소수는 서로소)
        // 3. Moduling : 반복문, 공통화, 특징 활용

        int a = 0;
        int limit = 100;
        String s = "";
        Uc f = new Uc();
        for (int i = 0; i < limit; i++) {
            a++;
            if (a == 1) System.out.println("1은 소수가 아닙니다.");
            else if (a == 2 || a == 3 || a == 5 || a == 7) System.out.println(a + "는 소수입니다.");
            else {
                // 3-1. 짝수가 아닌가?
                if (a % 2 == 0) System.out.println(a + "는 소수가 아닙니다.");
                    // 3-2. 3의 배수가 아닌가?
                else if (a % 3 == 0) System.out.println(a + "는 소수가 아닙니다.");
                    // 3-3. 5의 배수가 아닌가?
                else if (a % 5 == 0) System.out.println(a + "는 소수가 아닙니다.");
                    // 3-4. 7의 배수가 아닌가?
                else if (a % 7 == 0) System.out.println(a + "는 소수가 아닙니다.");
                    // 2, 3, 5, 7까지의 배수만 비교하는 이유 : 10보다 큰 소수인 11의 거듭제곱 = 121이므로 100을 넘어감, 즉 소수 범위 내에서는 2, 3, 5, 7의 배수만 찾으면 소거법으로 다른 소수들을 전부 찾을 수 있음
                else {
                    s = f.gcd(a, 2) == 1 ? "소수입" : "소수가 아닙";
                    System.out.println(a + "은 " + s + "니다.");
                }
            }
        }
    }
}

결과

추가 문제

• 특정 수 N이 소수인지 판별하시오.

문제 분석

• 2, 3은 무조건 소수

• 1은 소수가 아님

• 2의 배수(짝수)는 소수가 아님 : 경우 제외 가능

코드 작성

package algo;

public class Pn02 {
    public static void main(String[] args) {
        int a = 1;
        int count = 0;
        int N = 15;
        String s = "";
        // N = 짝수인 경우를 전부 제외 + 홀수로만 약수 비교 > O(n/2)
        // i의 증가분을 늘리지 않을 경우 (i++로 놔둘 때), i < (N+1)/2
        for (int i = 0; i < N; i = i + 2) {
            if (N == 1) System.out.println(N + "은 소수가 아닙니다.");
            else if (N == 2) System.out.println(N + "은 소수입니다.");
            else if (N == 3) System.out.println(N + "은 소수입니다.");
            else if (N % 2 == 0) System.out.println(N + "은 소수가 아닙니다.");
            else {
                if (N % a == 0) {
                    System.out.println(a + "는 약수입니다.");
                    count++;
                } else {
                    System.out.println(a + "는 약수가 아닙니다.");
                }
            }
            a = a + 2;
        }
        System.out.println(N + "의 약수의 개수 : " + count);
        if (count == 2) System.out.println(N + "은 소수");
    }
}