소수판정 알고리즘 질문
뿡뿡몬
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 부분이 문제가 있는거 같네요. 저 부분이 있는 한 모든 수는 소수가 아닌 것으로 판명나게 될 것 같은데요.
번호 | 제 목 | 글쓴이 | 날짜 |
---|---|---|---|
2655416 | 고수님들 도움이 절실합니다. (2) | 세리 | 2024-05-19 |
2655361 | 엔터 입력받을때까지 기다리는 getchar (1) | 큰모음 | 2024-05-19 |
2655328 | 함수에서 포인터 (3) | 모아 | 2024-05-18 |
2655299 | 아이콘바꾸는법..? | 소 | 2024-05-18 |
2655271 | scanf 입력받으면 쭉 실행되는.. (5) | ComeOn | 2024-05-18 |
2655184 | 이 세개 프로그램좀 해결해주실.... 고수님들???? (3) | 말달리자 | 2024-05-17 |
2655129 | 다차원 배열 원소들 주소계산하는거 질문이요~ | 터전 | 2024-05-17 |
2655103 | AVRstudio MoveAxis. MoveLine 함수질문 | 앨버트 | 2024-05-16 |
2655072 | 콘솔창의 위치와 크기를 정하고 싶습니다. | 딥레드 | 2024-05-16 |
2655044 | 자료구조랑 online judge site에 대해서 질문있습니다... (1) | 뽀송뽀송 | 2024-05-16 |
2655016 | 별찍기 문제 중 이해안되는 부분이 있어요... | 도전중 | 2024-05-16 |
2654986 | 입력받은 성적을 배열에 저장하기 (3) | 안녕나야 | 2024-05-15 |
2654959 | ===========-이런거 미리 지정하는법 (1) | 김자영 | 2024-05-15 |
2654930 | 도와주십시요 ㅜㅜ 자료구조 ㅜㅜ | 도널드 | 2024-05-15 |
2654881 | PID 모듈 검색 부분 질문합니다 . | 이름없음 | 2024-05-14 |
2654850 | 조건에 만족하는 다음 수를 찾고 싶습니다. | 초엘 | 2024-05-14 |
2654790 | 두파일간 byte단위 txt파일 복사 中 | 슬찬 | 2024-05-14 |
2654768 | 사전만들기 입니다. | 여우By | 2024-05-13 |
2654716 | c언어 고수님들 답좀적어주세요 급합니다 ㅠㅠ | 한말글 | 2024-05-13 |
2654688 | c언어 ㅠㅠ 너 무 어려 워요 ㅠ 도와주세요!! | 별빛 | 2024-05-13 |