C/C++ 소수판별기

조회수 61회
#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 << ", ";
        }
    }
    
    • 결과

    이미지

    • 한마디만 참견… 왜 2의제곱근이냐 하면 예컨대 25가 소수인지 판별하기 위해서는 5까지만 나눗셈해보면 알수 있기 때문입니다. 약수의 갯수를 세는 과정을 생각해 보면 이해될 것입니다. 엽토군 2020.10.10 09:41

답변을 하려면 로그인이 필요합니다.

Hashcode는 개발자들을 위한 무료 QnA 사이트입니다. 계정을 생성하셔야만 답변을 작성하실 수 있습니다.

(ಠ_ಠ)
(ಠ‿ಠ)

ᕕ( ᐛ )ᕗ
로그인이 필요합니다

Hashcode는 개발자들을 위한 무료 QnA사이트 입니다. 계정을 생성하셔야만 글을 작성하실 수 있습니다.