C++ вопрос о простых числах

Ознакомьтесь с http://en.wikipedia.org/wiki/Prime_number и http://en.wikipedia.org/wiki/Primality_test

Простейший тест на простоту выглядит следующим образом: по входному числу n проверьте, делится ли любое целое число m от 2 до n − 1 на n. Если n делится на любое m, то n составное, в противном случае оно простое.

что касается вашего кода, вы не проверяли, введу ли я 2, что произойдет, а также вы ничего не вернули, если это простое число... вот почему оно всегда возвращает простое число, несмотря на то, что число составное. вот код ниже =>

#include<iostream>
using namespace std;
int main(){
    int pNumber, limit, x, r;               
    limit = 2;
    x = 2;

    cout << "Please enter any positive integer: " ;
    cin >> pNumber;

    if (pNumber < 0){
        cout << "Invalid. Negative Number. " << endl;
        return 0;
    }
    else if (pNumber == 0){   
        cout << "Invalid. Zero has an infinite number of divisors, and therefore neither composite nor prime." << endl;
        return 0;
    }
    else if (pNumber == 1){
        cout << "Valid. However, one is neither prime nor composite" << endl;
        return 0;
    }
    else if (pNumber == 2){
        cout << " Your number is prime" << endl;
        return 0;
    }
    else{
        while (limit < pNumber){
            r = pNumber % x;
            x++;
            limit++;

            if (r > 0){
                cout << "Your number is prime" << endl;
                return 0;
            }
            else{
                cout << "Your number is composite" << endl;
                return 0;
            }
        }
    }
    return 0;
}

Во-первых, вам захочется вырваться из цикла, когда вы найдете x, где pNumber % x == 0. Все, что вам нужно сделать, это найти один множитель pNumber больше 1 и меньше pNumber, чтобы доказать, что он не является простым — нет смысла искать дальше. Если вы прошли весь путь до x = pNumber, не найдя ни одного, то вы знаете, что pNumber — простое число. На самом деле, даже если вы доберетесь до квадратного корня из pNumber, не найдя ни одного, это простое число, поскольку, если оно имеет множитель больше этого, оно должно иметь множитель меньше этого. Есть смысл?

Я не знаю, чему вас учили до сих пор, но мой учитель дискретной математики был поклонником Тест Миллера-Рабина. Это довольно точный тест, который очень легко закодировать, в нескольких базовых тестах у вас есть очень незначительный шанс, что у вас есть Номер Кармайкла. Если вы не продвинулись так далеко в своих исследованиях, я бы просто придерживался некоторых основных правил деления чисел.

Простейший метод для заданного числа n , если оно полностью делится на любое число от 2 до sqrt (n), это составное или простое число.

Привет, я сделал это также без использования заголовочного файла math.h .... Использовал компилятор turboc. Следующая программа проверяет, является ли число простым или составным.

                   #include<iostream.h>
                   #include<conio.h>
                   class prime
                             {
                                int a;
                                public:
                                     void check();

                             };
                             void prime::check()
                                                 {
                                                      cout<<"Insert a number";
                                                      cin>>a;
                                                      int count=0;
                                                      for(int i=a;i>=1;i--)
                                                         {
                                                            if(a%i==0)
                                                                    {
                                                                      count++;
                                                                     }
                                                         }
                                                             if(count==1)
                                                                      {
                                      cout<<"\nOne is neither prime nor composite";
                                                                       }
                                                             if(count>2)
                                                                       {
                                      cout<<"\nThe number is composite " ;
                                                                       }
                                                             if(count==2)
                                                                       {
                                      cout<<"\nThe numner is prime";
                                                                       }
                                 }

                                void main()
                                          {
                                            clrscr();
                                            prime k;
                                            k.check();
                                            getch();
                                          }