소수판정 알고리즘 질문
뿡뿡몬
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 부분이 문제가 있는거 같네요. 저 부분이 있는 한 모든 수는 소수가 아닌 것으로 판명나게 될 것 같은데요.
번호 | 제 목 | 글쓴이 | 날짜 |
---|---|---|---|
2656991 | 멀티쓰레드 예제 하나만요. (3) | 키움 | 2024-06-02 |
2656966 | 문자열 상수 저장메모리 (5) | 은별 | 2024-06-02 |
2656912 | 퀵정렬인데 급해요 ㅠㅠ | 큰돌찬 | 2024-06-02 |
2656767 | 초보입니다.. (1) | 플랜 | 2024-05-31 |
2656744 | 재귀함수 공부하다 이해가 안가서 질문드려요 (10) | PinkPearl | 2024-05-31 |
2656717 | 10진수를 2진수로 바꾸는 프로그램인데요 (3) | 감춰왔던 | 2024-05-31 |
2656686 | 포인터의 메모리값에 문자열넣기가 원래 안되나요..? | 심플이 | 2024-05-31 |
2656658 | 두가지 질문...(요약하기가 어렵내요... 죄송합니다..) | 한봄찬 | 2024-05-30 |
2656583 | 배열에 주소값대입 왜!!!!!!!!!!! (6) | 갅쥐누뉨 | 2024-05-30 |
2656555 | C언어 인데요 EOF에 대해서에여 알고리즘.. | 루라 | 2024-05-29 |
2656531 | 과제가왔는데 문제이해조차못하겠네요.. (2) | 다온 | 2024-05-29 |
2656502 | 비트 연산자 부분 질문드려요... (1) | 진주 | 2024-05-29 |
2656474 | c언어 왕초보인데요.. (4) | 예님 | 2024-05-29 |
2656444 | switch 문 대신에 다른 것을 사용하는 방법 (1) | 맺음새 | 2024-05-28 |
2656365 | for문하나로 1부터 100까지 5의배수 아닌 수들의 합을 구하는 프로그램 질문입니다. (7) | 똘끼 | 2024-05-28 |
2656309 | 구조체를 배열로 여러개만든뒤 함수에서 사용하는법? | 눈내리던날 | 2024-05-27 |
2656280 | c언어 프로그램 틀좀 잡아주실수 있는분.. (2) | 별하 | 2024-05-27 |
2656247 | 질문이 있는데요... | 시원 | 2024-05-27 |
2656218 | 함수 반환하는거 질문 ㅠ | 스릉흔다 | 2024-05-26 |
2656166 | 갑자기 증가하거나 감소하는 부분 처리. (2) | 마디 | 2024-05-26 |