입력받은 자연수의 소수 판별

코드스테이츠 코플릿 문제 中

• 자연수 num을 입력받고, num이 소수인지의 여부를 판별 해 boolean으로 반환한다.
• 먼저 if문으로 필터링을 한다. 
• 2는 소수이므로 바로 true, 1 이거나 2로 나눴을때의 나머지가 0 인지 확인

 

내가 한 방법

{

// 2는 소수라 바로 true를 리턴한다.
if ( num == 2)  
return true;


// 1이거나 2로 나눴을 떄 나머지가 0 이면 소수가 아니므로 false를 리턴한다.
if (num == 1 || num % 2 == 0)  
return false;


// 2부터 입력받은 자연수 사이의 모든 숫자를 하나씩 나눠서 나머지가 0인지 판별
for (int i = 2; i <num; i++) 
{
if(num % i == 0) return false;
}

//위 for문을 빠져 나오는 경우, 해당 자연수는 소수이다.
return true;
}

위와 같은 코드는 작동은 잘 되지만 입력받은 자연수가 큰 경우에는 속도가 느리다는 단점이 있다. 만약 입력받은 자연수가 200억이라면?

 

---

 

더 효율적인 방법

조금 더 효율적으로 코드를 짜 본다면 위의 for문을 입력받은 수의 제곱근을 응용해서 동작 속도를 절반가량 줄일 수 있다. for문을 제외한 코드는 위와 동일하다.

for ( int i = 3; i <= (int)(Math.sqrt(num)); i+= 2)
{
if(num % i == 0) 
        return false;
}

// 짝수는 위의 if문에서 전부 필터링 했으므로 홀수만 확인하면 된다.

// 대칭이 되는 패턴이 있다. 
// 예) 숫자 81은 [1 3 9 27 81] 의 약수를 갖는데, 제곱근 9를 기준으로 대칭을 이룬다.

// 따라서 제곱근을 기준으로 앞부분만 확인해도 전체를 돈 것과 같은 결과가 나온다.