[Java] 35. 소수 판별

1. 노가다 코드

package algo;

// 1. 요구사항
// 소수 구하기
// 100은 소수인가요 ?

// 2. 비지니스 분석 (약수가 2개 = 1과 자기 자신(N)) 정상, 비정상 테스트, 예외는 예외처리
// N = 1 (X)
// 1이 들어올 수 없어요.
// N = 2 (X)
// 2는 소수 입니다.
// N = 3 (X)
// 3은 소수 입니다.

// N = 4
// 2는 약수 4 % 2 == 0
// 3은 아님 4 % 3 != 0
// 4는 약수 4 % 4 == 0

// N = 5
// 2는 아님 5 % 2 != 0
// 3은 아님 5 % 3 != 0
// 4는 아님 5 % 4 != 0
// 5는 약수 5 % 5 == 0

public class Sosu01 {
    public static void main(String[] args) {

        int N = 7;

        if (N == 1) {
            System.out.println("1이 들어올 수 없습니다.");
            return;
        }

        // 변수 : 1,2,3 변수 :약수, 아님, (N바퀴)
        System.out.println("1은 약수");
        System.out.println("2은 아님");
        System.out.println("3은 아님");
        System.out.println("4은 아님");
        System.out.println("5은 아님");
        System.out.println("6은 아님");
        System.out.println("7은 약수");
    }
}

2. 공통 모듈 찾기

package algo;

public class Sosu02 {
    public static void main(String[] args) {

        int N = 7;

        if (N == 1) {
            System.out.println("1이 들어올 수 없습니다.");
            return;
        }

        // 변수 : 1,2,3 변수 :약수, 아님, (N바퀴)
        int a = 1;
        String s = "";

        s = N % a == 0 ? "약수" : "아님";
        System.out.println(a + "은 " + s);

        a++;
        s = N % a == 0 ? "약수" : "아님";
        System.out.println(a + "은 " + s);

        a++;
        s = N % a == 0 ? "약수" : "아님";
        System.out.println(a + "은 " + s);

        a++;
        s = N % a == 0 ? "약수" : "아님";
        System.out.println(a + "은 " + s);

        a++;
        s = N % a == 0 ? "약수" : "아님";
        System.out.println(a + "은 " + s);

        a++;
        s = N % a == 0 ? "약수" : "아님";
        System.out.println(a + "은 " + s);

        a++;
        s = N % a == 0 ? "약수" : "아님";
        System.out.println(a + "은 " + s);
    }
}

3. 공통 모듈 찾아서 코드 줄이기

package algo;

// O(N) 빅오 표기법
public class Sosu03 {
    public static void main(String[] args) {

        int N = 4999;

        if (N == 1) {
            System.out.println("1이 들어올 수 없습니다.");
            return;
        }

        // 변수 : 1,2,3 변수 :약수, 아님, (N바퀴)
        int a = 1;
        String s = "";
        int count = 0;

        for (int i = 0; i < N; i++) {
            s = N % a == 0 ? "약수" : "아님";
            count = N % a == 0 ? count + 1 : count;
            System.out.println(a + "은 " + s);
            a++;
        }

        if (count == 2) {
            System.out.println(N + "은 소수 입니다. ");
        } else {
            System.out.println(N + "은 소수가 아닙니다.");
        }
    }
}

4. 완성된 코드

package algo;

// O(N/2)
public class Sosu04 {
    public static void main(String[] args) {
        int N = 17;

        if (N == 1) { // 1은 소수 아님
            System.out.println("1이 들어올 없습니다.");
            return;
        }

        if (N == 2) { // 2는 소수
            System.out.println("2는 소수");
            return;
        }

        if (N % 2 == 0) { // 2를 제외한 짝수는 결국 소수가 아니기 때문에
            System.out.println(N + "은 소수가 아닙니다");
            return;
        }

        // 변수 :1,2,3 변수 : 약수, 아님, N바퀴
        int a = 1;
        String s = "";
        int count = 0;


        // N=3 -> N-1  => 3-1
        // N=5 -> N-2  => 5-2
        // N=7 -> N-3  => 7-3
        // N=9 -> N-4  => 9-4

        // N=3 -> 2 [0,1,2]
        // N=5 -> 3 [0,1,2,3,4]
        // N=7 -> 4 [0,1,2,3,4,5,6]
        // N=9 -> 5 [0,1,2,3,4,5,6,7,8]

        // N=15, i=0 -> a=1 -> count=1 -> 약수
        //       i=2 -> a=3 -> count=2 -> 약수
        //       i=4 -> a=5
        //       i=6 -> a=7
        //       i=8 -> a=9
        //       i=10 -> a=11
        //       i=12 -> a=13
        //       i=14 -> a=15
        for (int i = 0; i <= N; i = i + 2) { // [N=3, for=2] , [N=5, for=3], [N=7, for=4], [N=9, for=5]
            s = N % a == 0 ? "약수" : "아님";
            count = N % a == 0 ? count + 1 : count;
            System.out.println(a + "은 " + s);


            if (count == 2 && N != a) {
                count = -1;
                break;
            }
            a = a + 2;
        }


        System.out.println("count : " + count);

        if (count == 2) {
            System.out.println(N + "은 소수입니다");
        } else {
            System.out.println(N + "은 소수가 아닙니다");
        }
    }
}