수다닷컴

C로 배우는 알고리즘에서 소수를 구하려면 다음과 같은 알고리즘이 있다고 합니다.

int prime( int n )
{
for ( int i = 2 ; i n ; i++ )
if ( n % i == 0 )
return false;
return true;
}

이 알고리즘은 이해가 갑니다. 2부터 n-1 까지 나누어 보는..

하지만 제곱근을 이용한 소수판정은 이해가 안될 뿐더러 오답도 많은 것 같습니다.

int prime ( int n )
{
int i=2, sqrn = (int) sqrt(n); // 정수에 대입함으로서정수부분만 남게됨ex) 루트11 = 3.
for (; i = sqrn ; i++ ) // 2,3의 수를 나누어봄
if (n % i == 0 ) // 정수부분만 남은 3에 3을 나누면 나머지는 0
return false; // 11은 소수가 아님... 뭥미?...
return true;
}

대략 이런 결과가 나올것 같은데 어째서 소수를 잘 판정해내는지 이해가 안가는데요...

신청하기