23. [JAVA] 소수 구하기에 대해서(Math.sqrt란?)

 

[ 참조 블로그 ] 

 

https://st-lab.tistory.com/81

JAVA [자바] - 소수 구하는 알고리즘 및 구현

 

 

 

알고리즘을 공부하던 중 소수 구하기에 관한 알고리즘에 대해서 알게 되었다

 

하지만 수학과는 연관성이 1도 없던 나는 소수라는 것부터 무슨 뜻인지 알지 못하였고

 

공부를 하면서 차츰 알게 되었고 그에 대한 내용을 정리하고자 한다

 

---

 

[ 소수 란 ? ]

 

소수란?

 

간단하게 이야기하자면

 

1과 자기 자신만을 약수로 가지는 숫자를 의미한다

 

 

그러면 여기서 나같이 수학을 전혀 모르는 사람은 약수가 뭔지를 네이버에 검색해보게 된다

 

 

약수란?

 

어떠한 숫자로 나누어 떨어지는 숫자를 이야기한다

 

 

이렇게 말해도 뭔가 이상할 것이다

 

예를 들어보자

 

15라는 숫자가 있다

 

15는

 

1 - 15

3 - 5

 

라는 약수를 가지게 된다

 

즉, 15는 1 - 15 / 1과 자기 자신을 제외하고도 3 - 5라는 약수를 가지고 있기에

 

15는 소수가 아니다

 

 

반대로 13을 보자

 

13은 

 

1 - 13

 

만을 약수로 가진다

 

1과 자기 자신 만을 약수로 가지기에

 

13은 약수이다

 

 

그렇다면 4는 어떨까??

 

4는

 

1 - 4

2 - 2

 

를 약수로 가진다

 

2 - 2는 2라는 숫자를 2번 곱해도 4가 나온다는 뜻인데

 

미묘하게 아닐 것 같지만 

 

4는 1,2,4를 약수로 가지기에

 

소수가 아니다

 

 

그렇다면 소수의 뜻은 알았다면

 

우리는 어떤 식으로 소수를 알 수 있는 알고리즘을 만들 수 있을까?

 

 

 

 

 

1. 기본적인 소수 구하기 알고리즘

 

package Algorithm.One;

import java.util.*;


public class Main {


        public static void main(String[] args) {

            Scanner in = new Scanner(System.in);

            is_prime(in.nextInt());

        }

        // 소수 판별 메소드 
        public static void is_prime(int number) {

            // 0 과 1 은 소수가 아니다
            if(number < 2) {
                System.out.print("소수가 아닙니다");
                return;
            }

            // 2 는 소수다
            if(number == 2) {
                System.out.print("소수입니다");
                return;
            }


            for(int i = 2; i < number; i++) {

                // 소수가 아닐경우
                if(number % i == 0) {
                    System.out.print("소수가 아닙니다");
                    return;
                }
            }
            // 위 반복문에서 약수를 갖고 있지 않는경우 소수다.
            System.out.print("소수입니다");
            return;
        }
        
}

 

 

해당 알고리즘에서 주목해야할 점은

 

for(int i = 2; i < number; i++) {

    // 소수가 아닐경우
    if(number % i == 0) {
        System.out.print("소수가 아닙니다");
        return;
    }
}

 

이 부분이다

 

1은 자기 자신만을 가질 수 있기에 제외되고 2부터 해당 숫자의 전까지 숫자를 나눠서 나머지가 있는지 체크한다

 

나머지가 없으면 약수로서의 효과가 있기에 소수가 아니여서 소수가 아니고

 

만약 모든 값이 나머지를 배출한다면 그 숫자는 소수이다

 

 

 

2. 에라토스테네스의 체 방법

 

 

 

에라토스테네스의 체

 

라는 알고리즘 방법이 있다

 

2부터 구할 숫자 까지의 배열을 만든 뒤

 

 √N 이하까지 반복하여 자연수들 중 k를 제외한 k의 배수들을 제외시킨다

 

 

무슨 말이냐

 

만약 16까지의 값중 소수인 값을 구한다고 쳐보자

 

 

내가 말하고도 말이 어렵다 

 

하지만 코드를 보면 이해가 간다

 

코드를 보도록 하자

 

 

[ 코 드 ]

 

public static boolean[] prime;  // 소수를 체크할 배열
   
    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);

        int N = in.nextInt();

        make_prime(N);

        for(int i = 0; i < prime.length; i++) {
            if(prime[i] == false) {    // 소수(false)일 경우 출력
                System.out.println(i);
            }
        }
    }

 

먼저 

 

prime [ ] 배열은 true 이면 소수가 아니고 false일 때는 소수라는 표시를 해두는 배열이다

 

그렇기에 prime[ i ] = false이면 데이터를 출력한다

 

 

그렇다면 make_prime(N) 메소드를 보도록 하자

 

 

 

 // N 이하 소수 생성 메소드
      public static void make_prime(int N) {

          prime = new boolean[N + 1];  // 0 ~ N

/*
소수가 아닌 index = true
소수인 index = false
*/

 

먼저 

 

prime 배열을 선언해주는데 해당 숫자에 + 1을 해줘서 0번 부터 계산하는 배열의 계산을 간편하게 해주도록 한다

 

 

   // 2 미만의 N 을 입력받으면 소수는 판별할 필요 없으므로 바로 return
    if(N < 2) {
        return;
    }

    prime[0] = prime[1] = true;


    // 제곱근 함수 : Math.sqrt()
    for(int i = 2; i <= Math.sqrt(N); i++) {

        // 이미 체크된 배열이면 다음 반복문으로 skip
        if(prime[i] == true) {
            continue;
        }

        // i 의 배수들을 걸러주기 위한 반복문
        for(int j = i * i; j < prime.length; j = j+i) {
            prime[j] = true;
        }
    }

}

 

만약 N이 2 이하이면 바로 반환 1은 약수가 될 수 없다

 

0, 1은 약수가 될 수 없으니 true로 설정해두고 난 뒤

 

반복문을 시작한다

 

 

 

2부터 Math.sqrt(N)

 

여기서 Math.sqrt( ) 가 뭔지 모르는 사람들이 많을 것 이다

 

 

[ Math.sqrt( )란 ? ]

 

제곱근 메소드인데

 

루트 처리해주는 것이다

 

16은 4 4

 

25는 5 5

 

물론 나누어떨어지지 않는 것들은

 

4.555555 이런식으로 소수점이 나오게 된다

 

조금 더 예를 들어보자면 19 같은 경우에는

 

4.5XXXX 라는 숫자 이기에 4까지는 i가 반복되게 된다는 것에만 주의하자

 

 

for(int i = 2; i <= Math.sqrt(N); i++) {

    // 이미 체크된 배열이면 다음 반복문으로 skip
    if(prime[i] == true) {
        continue;
    }

    // i 의 배수들을 걸러주기 위한 반복문
    for(int j = i * i; j < prime.length; j = j+i) {
        prime[j] = true;
    }
}

 

 

조금 더 상세히 보도록 하자

 

만약 16이라는 숫자를 넣었다면

 

i = 2 , 3 , 4로 총 3번 루프하게 되고

 

prime[ i ] 가 true면 넘어가고 아니면 진행한다

 

i = 2 일 때  j = 4 ~ 16 까지 j + 2를 진행

i = 3 일 때  j = 9 ~ 16 까지 j + 3를 진행

i  = 4 일 때 j = 16만 진행 

 

하면 끝이다

 

i = 2 일 때

 

[ 4 , 6 , 8 , 10 , 12 , 14 , 16]

 

i = 3 일 때

 

[ 9 , 12 , 15] = 12는 이미 진행했기에 처리 X

 

i = 4 일 때

 

16을 true 처리해야되지만 16은 이미 true이기에 continue로 반복문 종료된다

 

그렇게 처리 되고 난 뒤의 배열을 보면

 

[ 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16] 

 

에서

 

[ 2 3 5 7 11 13 ]

 

만이 남게 되고 해당 숫자는 소수임을 알 수 있다

 

소수 알고리즘은 이런 식으로 처리 된다고 한다