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

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

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

Моя собственная функция 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.*/ } в __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.*/ } по __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.*/ } по __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.*/ } в __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 миллиардов.

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

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

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

питон

 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; 

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

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

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

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

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

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

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

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

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

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

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

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

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

 // PrimeDef.cpp : Defines the entry point for the console application. // #include "stdafx.h" #include #include 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; } 

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

 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; 

}

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

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

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

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

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