C/C++ 소수판별기
조회수 988회
#include <iostream>
using namespace std;
int main(){
int begin, end, i;
int condition = 0;
cout << "Enter two integers between range 1 to 100" <<endl;
cin >> begin >> end;
while(begin <0 || end > 100)
{
cout << "Enter two integers again please" << endl;
cin >> begin >> end;
}
for ( i = begin; i <= end; i++ ) {
for (int j = 2; j <= i/2; j++ ) {
if (i % j == 0) {
condition= 1;
break;
}
else {
break;
}
}
if (condition)
cout << "The number " << i << " is not prime number" << endl;
else
cout << "The number " << i << " is prime number" << endl; } }
소수판별기 프로그램을짤때, 사람들이 두번째반복문에서 (int j = 2; j <= i/2; j++ )라는 조건식을 쓰던데, 왜 j <=i/2 라는 조건을 쓰는건가요? 그리고 이프로그램에서 소수인것도 소수가아니라고 출력하는데 이유가 무엇인지 알수있을까요?
1 답변
-
소수를 구하는 방법은 여러가지가 있습니다.
위 코드처럼 어떤 수를 2부터 시작해서 나누어 떨어지는가로 소수를 판단하는 방법도 있습니다.
이런 방법은 숫자를 x라고 했을 때 2부터 루트(x)까지만 체크하면 됩니다. 수학적인 내용이라서 왜 거기까지 해야하는지는 제가 제대로 설명드리기가 어렵습니다.
그래서 원래는 2부터 루트(x)까지 체크를 하면 되는데, 위 코드는 루트 구하기가 번거롭다 보니깐 x/2까지 체크한 것입니다. 루트(x)보다 x/2가 좀더 크니까 소수를 구하는데는 문제가 안생기는 거죠.
코드를 보니깐 문제가 조금 있네요.
아래 코드 참고하세요.
- 코드
#include <iostream> using namespace std; int main() { int begin, end; int condition = 0; cout << "Enter two integers between range 1 to 100" << endl; cin >> begin >> end; while (begin < 0 || end > 100) { cout << "Enter two integers again please" << endl; cin >> begin >> end; } for (int i = begin; i <= end; i++) { condition = 0; if (i == 1) condition = 1; for (int j = 2; j <= (i / 2); j++) { if (i % j == 0) { condition = 1; break; } } /* if (condition) cout << "The number " << i << " is not prime number" << endl; else cout << "The number " << i << " is prime number" << endl; */ if (condition == 0) cout << i << ", "; } }
- 결과
-
(•́ ✖ •̀)
알 수 없는 사용자
댓글 입력