소수판정 알고리즘 질문
뿡뿡몬
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 부분이 문제가 있는거 같네요. 저 부분이 있는 한 모든 수는 소수가 아닌 것으로 판명나게 될 것 같은데요.
번호 | 제 목 | 글쓴이 | 날짜 |
---|---|---|---|
2653985 | 실수 자료형 표현범위있잖아요 (1) | 패틱 | 2024-05-06 |
2653957 | 뭐가틀린건가요?.. (2) | 볼1매그녀 | 2024-05-06 |
2653934 | malloc을 이용한 출력 (1) | 하예 | 2024-05-06 |
2653906 | 숫자 야구 게임인데요.. (2) | 상큼한캔디 | 2024-05-06 |
2653883 | 구조체 질문이요.. 연결리스트. (1) | 별 | 2024-05-05 |
2653802 | 배열에 저장된 데이터와 원하는 데이터비교하는것좀.. | 리카 | 2024-05-05 |
2653727 | 고수님들 봐주세요~ (2) | 아담 | 2024-05-04 |
2653702 | C언어 의 단계가 어떻게 되나요???????????????? (3) | 길가온 | 2024-05-04 |
2653645 | 저....while인데..이게무슨뜻인지좀.. | 설희 | 2024-05-03 |
2653613 | 성별변수 | 뿡뿡 | 2024-05-03 |
2653584 | 16진수 변환 관련 질문 드립니다. | 매미꽃 | 2024-05-03 |
2653557 | 한글 완성형과 조합형의 전환 | 해지개 | 2024-05-02 |
2653506 | void형 포인터 이해안가요 ㅠㅠ (2) | 뭘봐요 | 2024-05-02 |
2653482 | 패턴매칭에 대한 질문하나 올립니다 | 미투리 | 2024-05-02 |
2653452 | main 함수 매개변수 문의드립니다. (2) | 딥레드 | 2024-05-01 |
2653425 | 간단한 포인터 설명좀 해주세요 ㅠㅠㅠ | 차분나래 | 2024-05-01 |
2653400 | 플로우 차트 작성 질문입니다. (2) | 아인 | 2024-05-01 |
2653370 | c언어 해석 부탁드립니다 ㅠ | 악당 | 2024-05-01 |
2653345 | 분수의 덧셈 질문이요 | 하늘 | 2024-04-30 |
2653313 | //정수 n을 입력받아 1부터 n까지의 합을 구하는 프로그램// (6) | 거북이 | 2024-04-30 |