소수(prime number)인지 구하는 함수 구현하기

 

 

자연수에서 소수(prime number)는 1보다 큰 수 중에 1과 자기자신만을 약수로 가지는 수이다.

따라서 자신보다 작은 수(1 제외)로 나눴을 때 항상 나누어 떨어지지 않아서 나머지가 존재한다는 의미다.

소수를 구하는 함수를 자바 언어를 사용하여 구현해보았다.

 

복잡하지 않게 작성하면 이렇게 구현할 수 있다.

public boolean prime (int num) {
	if(num == 0 || num == 1) return false;
	if(num == 2) return true;
    for(int i = 2; i < num; i++){
       if(num % i == 0) return false;
    }
    return true;
}

 

함수의 형식은 매개변수로 소수인지 구할 숫자를 입력받고 소수인지 여부를 true/false로 반환하는 모양으로 만들었다.

소수인지 구하기 전에 0과 1은 일단 소수가 아니므로 false를 리턴하고 2는 소수이므로 true를 리턴한다.

그리고 1보다 큰 수인 2부터 num보다 작은 num - 1까지 나누어떨어지는지 확인한다.

중간에 한번이라도 나누어떨어지면 소수가 아니므로 false를 리턴하고

num - 1 까지 확인을 마치면 true를 리턴한다.

 

여기서 더 효율적으로 코드를 짤 수는 없을까?

 

약수를 확인할 때 항상 2개씩 짝이 지어진다.

예를 들어 40의 약수를 구해보면

1, 2, 4, 5, 8, 10, 20, 40 이다.

이때 1과 40, 2와 20, 4와 10, 5와 8 이렇게 2개씩 짝이 지어진다.

그렇다면 맨 끝까지 일일이 나눠서 확인할 필요없이 중간 수 까지만 확인하면 끝까지(num - 1) 확인한 것과 같은 결과 일 것이다.

그 중간 수는 어떻게 구하는가?

2 x 20, 4 x 10, 5 x 8 = 40

중간 수는 자기자신을 곱했을 때 40이 나오는 수이다!

다시 말해 40의 제곱근이다.

자바에서 제곱근을 구하려면 Math.sqrt() 를 사용하면 된다.

다음은 제곱근까지만 확인하도록 구현해보았다.

 

    public boolean prime (int num) {
        if(num == 0 || num == 1) return false;
        if(num == 2) return true;
        if(num % 2 == 0) return false;
        for(int i = 3; i <= Math.sqrt(num); i++)
            if(num % i == 0) return false;
        return true;
    }

 

이 함수가 맨 처음에 만든 함수보다 반복문에서 num의 제곱근 까지만 반복하므로 더 효율적이다.

 

 

+ 

여기서 추가로 이웃이신 닉님의 도움으로 더 간단하게 작성했습니다!

짝수는 2로 나눠서 확인했기 때문에 3부터 +2하면서 확인하면 됩니다.

    public boolean prime (int num) {
        if(num == 0 || num == 1) return false;
        if(num == 2) return true;
        if(num % 2 == 0) return false;
        for(int i = 3; i <= Math.sqrt(num); i += 2)
            if(num % i == 0) return false;
        return true;
    }

 

 

 

 

읽어주셔서 감사합니다.

좋은 하루 되세요 ^^

+닉님 감사합니다😃