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

Ответ 1

Вам нужно сделать еще несколько проверок. Прямо сейчас, вы только проверяете, делится ли число на 2. Сделайте то же самое для 2, 3, 4, 5, 6,... до number. Подсказка: используйте цикл.

После устранения этого вопроса попробуйте найти оптимизацию. Подсказка: вам нужно только проверить все числа до квадратного корня из числа

Ответ 2

bool isPrime(int number){

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

}

Ответ 3

Моя собственная функция IsPrime(), написанная и основанная на детерминированном варианте известного алгоритма Рабина-Миллера в сочетании с оптимизированным степенным форсированием, предоставляющим вам одну из самых быстрых основных функций тестирования.

__int64 power(int a, int n, int mod)
{
 __int64 power=a,result=1;

 while(n)
 {
  if(n&1) 
   result=(result*power)%mod;
  power=(power*power)%mod;
  n>>=1;
 }
 return result;
}

bool witness(int a, int n)
{
 int t,u,i;
 __int64 prev,curr;

 u=n/2;
 t=1;
 while(!(u&1))
 {
  u/=2;
  ++t;
 }

 prev=power(a,u,n);
 for(i=1;i<=t;++i)
 {
  curr=(prev*prev)%n;
  if((curr==1)&&(prev!=1)&&(prev!=n-1)) 
   return true;
  prev=curr;
 }
 if(curr!=1) 
  return true;
 return false;
}

inline bool IsPrime( int number )
{
 if ( ( (!(number & 1)) && number != 2 ) || (number < 2) || (number % 3 == 0 && number != 3) )
  return (false);

 if(number<1373653)
 {
  for( int k = 1; 36*k*k-12*k < number;++k)
  if ( (number % (6*k+1) == 0) || (number % (6*k-1) == 0) )
   return (false);

  return true;
 }

 if(number < 9080191)
 {
  if(witness(31,number)) return false;
  if(witness(73,number)) return false;
  return true;
 }


 if(witness(2,number)) return false;
 if(witness(7,number)) return false;
 if(witness(61,number)) return false;
 return true;

 /*WARNING: Algorithm deterministic only for numbers < 4,759,123,141 (unsigned int max is 4294967296)
   if n < 1,373,653, it is enough to test a = 2 and 3.
   if n < 9,080,191, it is enough to test a = 31 and 73.
   if n < 4,759,123,141, it is enough to test a = 2, 7, and 61.
   if n < 2,152,302,898,747, it is enough to test a = 2, 3, 5, 7, and 11.
   if n < 3,474,749,660,383, it is enough to test a = 2, 3, 5, 7, 11, and 13.
   if n < 341,550,071,728,321, it is enough to test a = 2, 3, 5, 7, 11, 13, and 17.*/
}

Чтобы использовать, скопировать и вставить код в начало вашей программы. Вызовите его, и он вернет значение BOOL, истинное или ложное.

if(IsPrime(number))
{
    cout << "It prime";
}

else
{
    cout<<"It composite";
}

Если у вас возникла проблема с компиляцией с "__int64", замените ее на "long". Он компилируется под VS2008 и VS2010.

Как это работает: В функции есть три части. Часть проверяет, является ли это одним из редких исключений (отрицательные числа, 1) и перехватывает запуск программы.

Часть вторая начинается, если число меньше 1373653, что является теоретическим числом, в котором алгоритм Рабина Миллера превзойдет мою оптимизированную функцию грубой силы. Затем идут два уровня Рабина Миллера, предназначенные для сведения к минимуму количества необходимых свидетелей. Поскольку большинство чисел, которые вы будете тестировать, составляют менее 4 миллиардов, вероятностный алгоритм Рабина-Миллера может быть детерминирован, проверяя свидетелей 2, 7 и 61. Если вам нужно перечислить 4-миллиардную кепку, вам понадобится большая и применить модификацию модуля или битового сдвига к функции power().

Если вы настаиваете на методе грубой силы, вот только моя оптимизированная функция IsPrime() для грубой силы:

inline bool IsPrime( int number )
{
 if ( ( (!(number & 1)) && number != 2 ) || (number < 2) || (number % 3 == 0 && number != 3) )
  return (false);

 for( int k = 1; 36*k*k-12*k < number;++k)
  if ( (number % (6*k+1) == 0) || (number % (6*k-1) == 0) )
   return (false);
  return true;
 }
}

Как работает эта грубая сила: Все простые числа (кроме 2 и 3) можно выразить в виде 6k + 1 или 6k-1, где k - положительное целое число. Этот код использует этот факт и проверяет все числа в виде 6k + 1 или 6k-1 меньше, чем квадратный корень из числа, о котором идет речь. Эта часть интегрирована в мою большую функцию IsPrime() (функция, показанная первой).

Если вам нужно найти все простые числа ниже числа, найдите все простые числа ниже 1000, загляните в сито Эратосфена. Еще один мой любимый.

В качестве дополнительной заметки мне бы хотелось, чтобы кто-либо реализовал алгоритм Eliptical Curve Method, который хотел увидеть, что реализовано на С++ некоторое время, я потерял свою реализацию. Теоретически, это даже быстрее, чем детерминированный алгоритм Рабина Миллера, который я реализовал, хотя я не уверен, что это верно для чисел до 4 миллиардов.

Ответ 4

Я бы предпочел взять sqrt и запустить foreach frpm 2 до sqrt + 1 if (input% number!= 0) return false; как только вы достигнете sqrt + 1, вы можете быть уверены в его преимуществе.

Ответ 5

Если вы знаете диапазон входов (который вы делаете, так как ваша функция принимает int), вы можете предварительно скопировать таблицу простых чисел, меньшую или равную квадратному корню из максимального ввода (2 ^ 31-1 в этом случае), а затем проверить делимость на каждое простое в таблице, меньшее или равное квадратному корню из числа.

Ответ 6

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

проверяет любое число, если его простое число

Ответ 7

С++

bool isPrime(int number){
    if (number != 2){
        if (number < 2 || number % 2 == 0) {
            return false;
        }
        for(int i=3; (i*i)<=number; i+=2){
            if(number % i == 0 ){
                return false;
            }
        }
    }
    return true;
}

Javascript

function isPrime(number)
{
    if (number !== 2) {
        if (number < 2 || number % 2 === 0) {
            return false;
        }
        for (var i=3; (i*i)<=number; i+=2)
        {
            if (number % 2 === 0){
                return false;
            }
        }
    }
    return true;
}

Python

def isPrime(number):
    if (number != 2):
        if (number < 2 or number % 2 == 0):
            return False
        i = 3
        while (i*i) <= number:
            if(number % i == 0 ):
                return False;
            i += 2
    return True;

Ответ 8

Этот код только проверяет, делится ли число на два. Для того чтобы число было простым, оно не должно быть равномерно делящимся на все целые числа, меньшие самого себя. Это можно наивно реализовать, проверяя, если он делится на все целые числа меньше floor(sqrt(n)) в цикле. Если вас это интересует, существует ряд гораздо более быстрых алгоритмов.

Ответ 9

Если вы ленивы и имеете много оперативной памяти, создайте сито Eratosthenes, которое представляет собой практически гигантский массив, из которого вы пнули все числа, которые не являются первичными. С этого момента каждый простой тест "вероятность" будет очень быстрым. Верхний предел для этого решения для быстрого результата - это объем вашей ОЗУ. Верхний предел для этого решения для более высоких результатов - это емкость вашего жесткого диска.

Ответ 10

Я выполняю тот же алгоритм, но различную реализацию, которая зацикливает на sqrt (n) с шагом 2 только нечетные числа, потому что я проверяю, что если он делится на 2 или 2 * k, он является ложным. Вот мой код

public class PrimeTest {

    public static boolean isPrime(int i) {
        if (i < 2) {
            return false;
        } else if (i % 2 == 0 && i != 2) {
            return false;
        } else {
            for (int j = 3; j <= Math.sqrt(i); j = j + 2) {
                if (i % j == 0) {
                    return false;
                }
            }
            return true;
        }
    }

    /**
     * @param args
     */
    public static void main(String[] args) {
        for (int i = 1; i < 100; i++) {
            if (isPrime(i)) {
                System.out.println(i);
            }
        }
    }

}

Ответ 11

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

 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;

 } 

Ответ 12

Кто-то выше имел следующее.

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;
}

Ответ 13

Смотрите программу здесь: http://www.cplusplus.com/forum/general/1125/

Ответ 14

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

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

Ответ 15

// PrimeDef.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include<iostream> 
#include<stdlib.h> 

using namespace std; 

const char PRIME = 176; 
const char NO_PRIME = 178; 
const int  LAST_VALUE = 2000;

bool isPrimeNumber( int value ) 
{
    if( !( value / 2 ) ) return false; 
    for( int i = 1; ++i <= value / 2; ) 
       if( 0 == value % i ) return false; 
    return true; 
} 

int main( int argc, char *argv[ ] ) 
{ 
    char mark;
    for( int i = -1, count = 1; ++i < LAST_VALUE; count++ )
    {               
       mark = NO_PRIME;
       if( isPrimeNumber( i ) ) mark = PRIME; 

       cout << mark;        
       if(i > 0 && !( count % 50 ) ) cout << endl; 
    } 
    return 0; 
}

Ответ 16

Если 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;
}

Ответ 17

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

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;
}

Ответ 18

У меня есть эта идея для поиска, если номер чист или нет:

#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;
}

Ответ 19

Это быстрый способ:

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

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

Ответ 20

//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;
     }
 }

Ответ 21

#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;
}

Ответ 22

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

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