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

최재원

Feb 12, 2025

Contents

1. 요구사항 처리과정 2. 변수 찾기 규칙 분석 1. 반복문으로 전체탐색 1~n 까지 2로 나누어지는 짝수를 제외 검색하는 숫자의 수가 반감 반복하는 횟수와 비교 숫자도 2단위 증가로 변경 O(√n)짝수 제외

❗

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

방법은 2가지

O(n)

O(√n)

노가다

❗

약수가 2개면 소수다.

1. 요구사항 처리과정


package algo;
// 1. 요구사항
// 100(N)은 소수인가?
// 1
// 2
// 3 위 3가지는 예외로 처리

// 2. 비지니스 분석 : 소수는 무엇인가? (약수가 1과 자기자신(N) - 2개)

// 3. 샘플링 노가다
// N=4 | 비정상 샘플링
// 1은 약수인가? 4 % 1 == 0
// 2는 약수인가? 4 % 2 == 0
// 3은 약수인가? 4 % 3 != 0
// 4는 약수인가? 4 % 4 == 0

//N=5 | 정상 샘플링
// 1은 약수인가 5 % 1 == 0
// 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;
        }
        if (N == 2) {
            System.out.println("2는 소수");
            return;
        }
        if (N == 3) {
            System.out.println("3는 소수");
            return;
        }

        // 변수: 1,2,3 | 변수:"약수","아님" | N바퀴
        System.out.println("1은 X");
        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;
        }
        if (N == 2) {
            System.out.println("2는 소수");
            return;
        }
        if (N == 3) {
            System.out.println("3는 소수");
            return;
        }

        // 변수: 1,2,3 | 변수:"약수","아님" | N바퀴

        int a = 1;
        String b = "약수";
        String c = "아님";
        System.out.println(a + "은 " + (N % a == 0 ? b : c));
        a++;
        System.out.println(a + "은 " + (N % a == 0 ? b : c));
        a++;
        System.out.println(a + "은 " + (N % a == 0 ? b : c));
        a++;
        System.out.println(a + "은 " + (N % a == 0 ? b : c));
        a++;
        System.out.println(a + "은 " + (N % a == 0 ? b : c));
        a++;
        System.out.println(a + "은 " + (N % a == 0 ? b : c));
        a++;
        System.out.println(a + "은 " + (N % a == 0 ? b : c));
        a++;
    }
}

규칙 분석

1. O(n) 방법

❗

모든 경우의 수를 다 조사(전체탐색)

정답

1. 반복문으로 전체탐색 1~n 까지


package algo;
// O(n)
public class Sosu03 {
    public static void main(String[] args) {
        int N = 498;

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

        // 변수: 1,2,3 | 변수:"약수","아님" | N바퀴

        int a = 1;
        String b = "약수";
        String c = "아님";
        int count = 0;

        for (int i = 0; i < N; i++) {
            System.out.println(a + "은 " + (N % a == 0 ? b : c));
            count = N % a == 0 ? count + 1 : count;
            a++;
        }

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

2. O(n/2)

❗

n이 짝수인 것을 제외시키고,(짝수는 무조건 2를 약수로 갖기 때문에 소수가 아니다)

n이 홀수일때만 검사하는데, 홀수는 2로 나눌수 없으니까, 반을 제외시킬수 있다.

정답


package algo;

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

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

2로 나누어지는 짝수를 제외 검색하는 숫자의 수가 반감


        if (N % 2 == 0) {
            System.out.println(N + "은 소수가 아닙니다.");
            return;
        }


        // 변수: 1,2,3 | 변수:"약수","아님" | N바퀴

        int a = 1;
        String b = "약수";
        String c = "아님";
        int count = 0;

        //    N -> for
        // 1. 3 -> 2
        // 2. 5 -> 3
        // 3. 7 -> 4
        // 4. 9 -> 5
        // 5. 11 -> 6
        // 6. 13 -> 7
        // 반복횟수는 N의 1/2

        // N = 15 -> i=0, a=1 -> count=1 -> 약수
        //           i=2, a=3 -> count=2 -> 약수
        //           i=4, a=5 -> count=2 -> 약수
        //           i=6, a=7 ->
        //           i=8, a=9 ->
        //           i=10, a=11 ->

반복하는 횟수와 비교 숫자도 2단위 증가로 변경


for (int i = 0; i < N; i = i + 2) { // [N = 3, for = 2],[N = 5, for = 3], [N = 7, for = 4]
            System.out.println(a + "은 " + (N % a == 0 ? b : c));
            count = N % a == 0 ? count + 1 : count;
            if (count == 2 && N != a) {
                count--;
                break;
            }
            a = a + 2;
        }

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

3. O(√n) 방법

❗

50이라면, 1*1, 2*2, 3*3, 4*4, 5*5, 6*6, 7*7 최악의 상황이라 하더라도 5번이면 끝남

제곱해서 N값 보다 작을때까지만 반복하면 됨.

약수의 대칭성 때문에 12라면 [1,2,3,4,6,12] 이니까 1,2,3과 4,6,12 가 대칭이다.

즉 3*3까지 검사하면 된다. 4*4는 12를 넘어간다.

루트50은 7.xxx 값을 가짐.

튜닝하면, 1과2는 제외하고 가능

더 튜닝하면 짝수는 안해도 됨. 실제로는 루트 n/2 이지만, 빅오 표시에서는 상수는 제외하기 때문에 여전히 시간 복잡도는 O(√n)

정답

O(√n)


public class Sosu08 {
    public static void main(String[] args) {
        // N = 29은 소수인가? (소수는 약수가 2개인 수이다)

        final int N = 19;

        if (N < 2) {
            System.out.println("N은 1보다 커야합니다.");
            return;
        }
        if (N == 2 || N == 3) {
            System.out.println(N + "은 소수입니다");
            return;
        }

        int a = 2;
        int r = 1;

        boolean isSosu = true;

        // i를 제곱한 값이 N보다 작거나 같을때까지 순회 :  O(루트N)
        // 4(a=2), 9(a=3), 16(a=4), 25(a=5) (4라운드까지 함) - 29보다 작으니까!!
        for (int i = 2; i * i <= N; i++) {
            System.out.println(r + "라운드..........");
            if (N % a == 0) {
                System.out.println("약수(a) : " + a);
                if (N == a) {
                    isSosu = true;
                } else {
                    isSosu = false;
                    break;
                }
            }
            a++;
            r++;
        }
        if (isSosu) System.out.println(N + "은 소수입니다");
        else System.out.println(N + "은 소수가 아닙니다");

    }
}

짝수 제외


public class Sosu08 {
    public static void main(String[] args) {
        // N = 29은 소수인가? (소수는 약수가 2개인 수이다)

        final int N = 131;

        if (N < 2) {
            System.out.println("N은 1보다 커야합니다.");
            return;
        }
        if (N == 2 || N == 3) {
            System.out.println(N + "은 소수입니다");
            return;
        }

        int a = 2;
        int r = 1;

        boolean isSosu = true;

        // i를 제곱한 값이 N보다 작거나 같을때까지 순회 :  O(루트N)
        // 4(a=2), 9(a=3), 16(a=4), 25(a=5) (4라운드까지 함) - 29보다 작으니까!!
        // i->2, i->4      | a->2, a->3 꽝
        // i->2, i->3 i->4 i->5 | a->2, a->3, a->4, a->5
        for (int i = 2; i * i <= N; i = i) {
            System.out.println(r + "라운드..........");
            if (N % a == 0) {
                System.out.println("약수(a) : " + a);
                if (N == a) {
                    isSosu = true;
                } else {
                    isSosu = false;
                    break;
                }
            }
            if (i < 3) {
                a++;
                i++;
            } else {
                a = a + 2;
                i = i + 2;
            }
            r++;
        }
        if (isSosu) System.out.println(N + "은 소수입니다");
        else System.out.println(N + "은 소수가 아닙니다");

    }
}

See more posts

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

노가다

1. 요구사항 처리과정

2. 변수 찾기

규칙 분석

1. O(n) 방법

정답

1. 반복문으로 전체탐색 1~n 까지

2. O(n/2)

정답

2로 나누어지는 짝수를 제외 검색하는 숫자의 수가 반감

반복하는 횟수와 비교 숫자도 2단위 증가로 변경

3. O(√n) 방법

정답

O(√n)

짝수 제외

More articles

[JAVA] 8. 필수 알고리즘 Ⅶ. 소인수분해

[JAVA] 8. 필수 알고리즘 Ⅵ. 서로소

[JAVA] 8. 필수 알고리즘 Ⅳ. 최소공배수(LCM)

[JAVA] 8. 필수 알고리즘 Ⅲ. 최대공약수(GCD)