Bestimmung, ob eine Zahl eine Primzahl ist

Sie tun müssen, etwas mehr Kontrolle. Jetzt, Sie sind nur zu überprüfen, ob die Zahl ist durch 2 teilbar. Tun Sie das gleiche für 2, 3, 4, 5, 6, ... bis zu number. Tipp: benutzen Sie eine Schleife.

Nachdem Sie dies beheben, versuchen der Suche nach Optimierungen.
Hinweis: Sie haben nur zu prüfen, alle zahlen bis zur Quadratwurzel der Zahl

Meine eigenen IsPrime () - Funktion geschrieben und auf der Grundlage der deterministischen Variante des berühmten Rabin-Miller-Algorithmus, kombiniert mit einem optimierten Schritt brute Force, so dass Sie eine der schnellsten prime Funktionen zu testen gibt.

__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.*/
}

Zu verwenden, zu kopieren und fügen Sie den code in das oben auf Ihrem Programm. Nennen Sie es, und es gibt einen BOOL-Wert, der entweder true oder false.

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

else
{
    cout<<"It's composite";
}

Wenn Sie ein problem kompilieren mit "__int64", ersetzen mit "lange". Es kompiliert einwandfrei unter VS2008 und VS2010.

Wie es funktioniert:
Es gibt drei Teile, um die Funktion. Teil prüft, um zu sehen, ob es ist eine der seltenen Ausnahmen (negative zahlen, 1), und fängt die Ausführung des Programms.

Teil zwei beginnt, wenn die Zahl kleiner als 1373653, die die theoretisch-Nummer wo der Rabin-Miller-Algorithmus zu schlagen meine optimierte brute-force-Funktion. Dann kommt zwei Ebenen der Rabin-Miller, entworfen, um zu minimieren die Anzahl der Zeugen benötigt. Wie die meisten zahlen, werden Sie die Tests sind unter 4 Milliarden, die probabilistischen Rabin-Miller-Algorithmus gemacht werden kann deterministisch durch die überprüfung von Zeugen 2, 7 und 61. Wenn Sie brauchen, um gehen über die 4-Milliarden-cap, benötigen Sie eine große Anzahl-Bibliothek, und legen Sie eine Modul-oder bit-shift Modifikation der power () - Funktion.

Wenn Sie darauf bestehen, auf eine brute-force-Methode, hier nur meine optimierte brute-force-IsPrime () - Funktion:

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

Wie diese brute-force-Stück funktioniert:
Alle Primzahlen (ausgenommen 2 und 3) kann ausgedrückt werden in der form 6k+1 oder 6k-1, wobei k eine positive ganze Zahl. Dieser code nutzt diese Tatsache, und tests alle zahlen der form 6k+1 oder 6k-1 weniger als die Quadratwurzel der Zahl in Frage. Dieses Stück ist integriert in meinem größeren IsPrime () - Funktion (die Funktion, die zuerst angezeigt).

Wenn Sie brauchen, um alle Primzahlen unterhalb einer Zahl, finden Sie alle Primzahlen unter 1000, schauen Sie in das Sieb des Eratosthenes. Ein weiterer Favorit von mir.

Als zusätzliche Anmerkung, ich würde gerne sehen, wer implementiert die Elliptische Kurve, Methode, Algorithmus, gefehlt, um zu sehen, dass in C++ implementiert, die für eine Weile jetzt, ich verlor meine Umsetzung davon. Theoretisch ist es sogar schneller als die deterministischen Rabin-Miller-Algorithmus implementiert habe ich, obwohl ich nicht sicher bin, ob das stimmt für die Nummern unter 4 Milliarden.

Wenn Sie wissen, die Auswahl der Eingänge (was Sie tun, da Ihre Funktion eine int), können Sie vorausberechnen eine Tabelle der Primzahlen kleiner oder gleich der Quadratwurzel der max-Eingang (2^31-1 in diesem Fall), und testen Sie dann für die Teilbarkeit von jedem prime in der Tabelle weniger als oder gleich der Quadratwurzel der Zahl gegeben.

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;

Wenn Sie faul sind, und haben eine Menge RAM, erstellen Sie eine Sieb des Eratosthenes das ist praktisch eine Riesen-array, aus dem Sie hinausgeworfen, alle zahlen, die nicht prim.
Ab dann ist jeder prime "Wahrscheinlichkeit" test wird super schnell.
Die Obere Grenze für diese Lösung für schnelle Ergebnisse ist der Betrag, den Sie RAM. Die Obere Grenze für diese Lösung für superslow Ergebnisse ist Ihre Festplatte die Kapazität.

Mathematik benutzen die ersten finden, die Quadratwurzel der Zahl, dann start-Schleife, bis die Nummer enden, die Sie erhalten, nachdem square wühlen.
überprüfen Sie für jeden Wert, ob die gegebene Zahl teilbar ist durch die Iteration mit dem Wert .wenn ein Wert teilt sich die angegebene Nummer, dann ist es keine Primzahl sonst prime.
Hier ist der code

 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;

 } 

Gibt es verschiedene Ansätze zu diesem problem.

Der "Naive" Methode: Versuchen Sie, alle (ungeraden) zahlen Sie bis (die Wurzel), die Nummer.

Verbesserte "Naive" Methode: Nur jeder ausprobieren 6n ± 1.

Probabilistische tests: Miller-Rabin, Solovay-Strasse, etc.

Welches Konzept zu Ihnen passt, hängt und was Sie tun, mit die prime.

Sie sollten wenigstens Lesen, auf Primality Testing.

Habe Ich Diese Idee Zu Finden, Wenn Dem Keine. Eine Primzahl ist oder Nicht:

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

Dies ist eine schnelle, effektive eins:

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

Wird es beginnen, finden eine teilbare Anzahl von n, beginnend mit 2. Sobald einer gefunden wird, wenn diese Anzahl gleich n, dann es ist prime, sonst ist es nicht.

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