05/06/22 [pair: java: 반복문: 3] 소수를 판별하는 여러가지 방법

isPrime

1이상의 자연수를 입력받아 소수면 true, 아니면 false를 리턴하기

 

Pair)

 

public boolean isPrime(int num) {
    int count = 0;
    for(int i=1; i<=num; i++){
        if(num%i == 0){
        count++;
        }
    }
    return count==2 ? true : false;
}

 

소수는 1과 자기 자신 외의 수로는 나누어지지 않는다. for문을 통해 1부터 자기 자신까지 전부 나누어보고 나머지가 0이라면 count에 +1을 하는 연산을 수행하게 했다. 소수의 정의에 따라 소수라면 count==2가 될 것이다. 따라서 count 값이 2인 경우 true(소수) 값을, 아닐 경우 false를 반환하는 코드를 작성했다.

 

개선 방안

 

위에 작성한 코드를 수행하는 경우, 만약 10000을 입력받는다면 for문에 의해 10000번의 % 연산을 수행해야 한다. 그러니 코드의 성능을 향상시켜보기로 한다.

 

1. 짝수는 소수가 될 수 없다.

 

public boolean isPrime(int num) {
    if(num==2) return true;
    if(num==1 || num%2==0) return false;
    for(int i=3; i<num; i++){
        if(num%i==0) return false;
    }
    //i<num: 1과 자신을 제외하고 나누어떨어지는 수가 있으므로 false
    return true;
}

 

2는 짝수지만 소수이므로 예외 처리를 먼저 해준다. 1 역시 경우 홀수이지만 소수가 아니므로 num이 짝수인 경우와 함께 묶어 false 값을 리턴하도록 처리한다. 이렇게 처리할 경우 num이 홀수인 경우에 대해서만 for문을 수행하게 되므로 처음 작성한 코드보다 수행할 연산이 대폭 줄어든다.

 

2. 약수는 대칭적이다.

 

소수가 아니라는 것은 약수가 존재한다는 것이다. 또한 이 약수들은 제곱근을 기준으로 대칭을 이룬다.

 

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

 

대칭을 이룬다는 것은 제곱근을 기준으로 제곱근 이전에 약수가 존재한다면 이후에도 약수가 존재할 것이라는 의미이다. 따라서 1번에 작성한 for문의 조건을 num의 제곱근 이전까지만 설정해도 동일한 결과를 얻을 수 있게 된다. 

 

---

Math.sqrt(double a)

a의 제곱근을 반환한다.

주의할 점은 int 값을 넣어줘도 double 값을 반환한다는 것. -> 결과값을 int로 얻고 싶다면 앞에 (int)를 붙여 수동 타입 변환을 해주어야 한다.

(reference)

Java sqrt() method with Examples - GeeksforGeeks

---

🐑 

많이 배웠다. 저는 걍 코드가 짧으면 최고인 줄 아는 멍청이였습니다.