Определение, является ли число простым

Question

Я просмотрел много кода на эту тему, но большинство из них выдает числа, которые являются простыми вплоть до входного числа. Однако мне нужен код, который только проверяет, является ли данный входной номер простым.

Вот что мне удалось написать, но оно не работает:

void primenumber(int number)
{
    if(number%2!=0)
      cout<<"Number is prime:"<<endl;
    else 
      cout<<"number is NOt prime"<<endl;
}

Буду признателен, если кто-нибудь даст мне совет, как правильно сделать эту работу.

Обновление

Я изменил его, чтобы проверить все числа в цикле for.

void primenumber(int number)
{
    for(int i=1; i<number; i++)
    {
       if(number%i!=0)
          cout<<"Number is prime:"<<endl;
       else 
          cout<<"number is NOt prime"<<endl;
    }  
}

Answer 1

Используйте математику, сначала найдите квадратный корень из числа, затем начните цикл до тех пор, пока не закончится число, которое вы получите после квадратного корня. проверьте для каждого значения, является ли данное число делимым на итеративное значение. Если любое значение делит данное число, то оно не является простым числом, в противном случае - простым. Вот код

 bool is_Prime(int n)
 {

   int square_root = sqrt(n); // use math.h
   int toggle = 1;
   for(int i = 2; i <= square_root; i++)
   {
     if(n%i==0)
     { 
        toggle = 0;
        break;
     }
   }

   if(toggle)
     return true;
   else
     return false;

 } 

Answer 2

У кого-то выше было следующее.

bool check_prime(int num) {
for (int i = num - 1; i > 1; i--) {
    if ((num % i) == 0)
        return false;
}
return true;
}

В основном это работало.Я только что проверил это в Visual Studio 2017. Он сказал бы, что все, что меньше 2, также является простым (так что 1, 0, -1 и т. Д.)

Вот небольшая модификация, чтобы исправить это.

bool check_prime(int number)
{
    if (number > 1)
    {
        for (int i = number - 1; i > 1; i--)
        {
            if ((number % i) == 0)
                return false;
        }
        return true;
    }
    return false;
}

Answer 3

//simple function to determine if a number is a prime number
//to state if it is a prime number


#include <iostream>

using namespace std;


int isPrime(int x);  //functioned defined after int main()


int main()
{
 int y;
    cout<<"enter value"<<endl;

    cin>>y;

    isPrime(y);    

  return 0;

 } //end of main function


//-------------function

  int isPrime(int x)
 {
   int counter =0;
     cout<<"factors of "<<x<<" are "<<"\n\n";    //print factors of the number

     for (int i =0; i<=x; i++)

     {
       for (int j =0; j<=x; j++)

         {
           if (i * j == x)      //check if the number has multiples;
                {

                  cout<<i<<" ,  ";  //output provided for the reader to see the
                                    // muliples
                  ++counter;        //counts the number of factors

                 }


          }


    }
  cout<<"\n\n";

  if(counter>2) 
     { 
      cout<<"value is not a prime number"<<"\n\n";
     }

  if(counter<=2)
     {
       cout<<"value is a prime number"<<endl;
     }
 }

Answer 4

Это быстрый эффективный метод:

bool isPrimeNumber(int n) {
    int divider = 2;
    while (n % divider != 0) {
        divider++;
    }
    if (n == divider) {
        return true;
    }
    else {
        return false;
    }
}

Он начнет находить делимое число n, начиная с 2. Как только он его найдет, если это число равно n, тогда это просто , иначе это не так.

Answer 5

Я использовал эту идею для определения, является ли номер основным или нет:

#include <conio.h> 
#include <iostream>
using namespace std;
int main() {
  int x, a;
  cout << "Enter The No. :";
  cin >> x;
  int prime(unsigned int);
  a = prime(x);
  if (a == 1)
    cout << "It Is A Prime No." << endl;
  else
  if (a == 0)
    cout << "It Is Composite No." << endl;
  getch();
}

int prime(unsigned int x) {
  if (x == 1) {
    cout << "It Is Neither Prime Nor Composite";
    return 2;
  }
  if (x == 2 || x == 3 || x == 5 || x == 7)
    return 1;
  if (x % 2 != 0 && x % 3 != 0 && x % 5 != 0 && x % 7 != 0)
    return 1;
  else
    return 0;
}

Answer 6

Я придумал это:

int counter = 0;

bool checkPrime(int x) {
   for (int y = x; y > 0; y--){
      if (x%y == 0) {
         counter++;
      }
   }
   if (counter == 2) {
      counter = 0; //resets counter for next input
      return true; //if its only divisible by two numbers (itself and one) its a prime
   }
   else counter = 0;
        return false;
}

Answer 7

Если n равно 2, оно простое.

Если n равно 1, оно не простое.

Если n четное, оно не простое.

Если n нечетно, больше 2, мы должны проверить все нечетные числа 3..sqrt (n) +1, если любое из этих чисел может делить n, n не простое, иначе n простое.

Для лучшей производительности рекомендую сито эратосфена.

Вот пример кода:

bool is_prime(int n)
{
  if (n == 2) return true;
  if (n == 1 || n % 2 == 0) return false;

  for (int i = 3; i*i < n+1; i += 2) {
      if (n % i == 0) return false;
  }

  return true;
}

Answer 8

Существует несколько различных подходов к этой проблеме.
Метод «Наивный»: Попробуйте все (нечетные) числа вплоть до (корень) числа.
Улучшенный метод «Наивный»: Попробуйте только каждые 6n± 1.
Вероятностные тесты: Миллер-Рабин, Соловай-Штрассе и т. Д.

Какой подход вам подходит, зависит от того, что вы делаете с простыми числами.
Вы должны хотя бы прочитать Проверка на первичность .

Answer 9

#define TRUE 1
#define FALSE -1

int main()
{
/* Local variables declaration */
int num = 0;
int result = 0;

/* Getting number from user for which max prime quadruplet value is 
to be found */
printf("\nEnter the number :");
scanf("%d", &num);

result = Is_Prime( num );

/* Printing the result to standard output */
if (TRUE == result)
    printf("\n%d is a prime number\n", num);
else
    printf("\n%d is not a prime number\n", num);

return 0;
}

int Is_Prime( int num )
{
int i = 0;

/* Checking whether number is negative. If num is negative, making
it positive */
if( 0 > num )
    num = -num;

/* Checking whether number is less than 2 */
if( 2 > num )
    return FALSE;

/* Checking if number is 2 */
if( 2 == num )
    return TRUE;

/* Checking whether number is even. Even numbers
are not prime numbers */
if( 0 == ( num % 2 ))
    return FALSE;

/* Checking whether the number is divisible by a smaller number
1 += 2, is done to skip checking divisibility by even numbers.
Iteration reduced to half */
for( i = 3; i < num; i += 2 )
    if( 0 == ( num % i ))
        /* Number is divisible by some smaller number, 
        hence not a prime number */
        return FALSE;

return TRUE;
}

Answer 10

if(number%2!=0)
      cout<<"Number is prime:"<<endl;

Код невероятно ложный.33, деленное на 2 - это 16 с напоминанием 1, но это не простое число ...