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

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

}

Answer 2

Моя собственная функция 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's 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's prime";
}

else
{
    cout<<"It's 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, давно хотел увидеть его реализованный в C ++, и я потерял свою реализацию. Теоретически, это даже быстрее, чем детерминированный алгоритм Рабина Миллера, который я реализовал, хотя я не уверен, верно ли это для чисел до 4 млрд.

Answer 3

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

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

Answer 4

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

Answer 5

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

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

Answer 6

C ++

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;

Answer 7

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

Answer 8

Я придерживаюсь того же алгоритма, но с другой реализацией, которая зацикливается на 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);
            }
        }
    }

}

Answer 9

Если вы ленивы и у вас много оперативной памяти, создайте сито Эратосфена , которое представляет собой практически гигантский массив, из которого вы выбросили все числа, которые не являются простыми. С тех пор каждый простой «вероятностный» тест будет супер быстрым. Верхним пределом для этого решения для быстрых результатов является объем вашей оперативной памяти. Верхним пределом этого решения для сверхнизких результатов является емкость вашего жесткого диска.

Answer 10

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