소수판정 알고리즘 질문
뿡뿡몬
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;
}
대략 이런 결과가 나올것 같은데 어째서 소수를 잘 판정해내는지 이해가 안가는데요...
-
미쁘다
if (n % i == 0 ) // 정수부분만 남은 3에 3을 나누면 나머지는 0
현재 n은 11임 3에 3을 나누는게 아니라 11을 3으로 나누는거조... -
유1혹
아하, 주석 때문에 잘 못 이해했네요.
n%i 에서 n은 3 이 아니라 11인데요. -
아더
저 부분이 왜 문제가 되죠? 기하평균 값까지만 약수가 없으면 그 이상은 해 볼 필요가 없다는 의미이므로 올바른 로직입니다.
-
글고운
i = sprn 부분이 문제가 있는거 같네요. 저 부분이 있는 한 모든 수는 소수가 아닌 것으로 판명나게 될 것 같은데요.