Déterminer si un nombre est premier

Vous avez besoin de faire un peu plus de la vérification. Maintenant, vous êtes seulement de vérifier si le nombre est divisible par 2. Faire de même pour 2, 3, 4, 5, 6, ... jusqu'à number. Astuce: utilisez un boucle.

Après vous résoudre ce problème, essayez de regarder pour les optimisations.
Astuce: Vous n'avez qu'à vérifier tous les numéros jusqu'à la racine carrée du nombre

OriginalL'auteur Pablo Santa Cruz

Mon propre IsPrime() de la fonction, écrit et basé sur la déterministe variante de la célèbre Rabin-Miller algorithme, combiné avec l'optimisation de l'étape de force brute, de vous en donner un de la manière la plus rapide de premier les fonctions de test.

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

D'utiliser, de copier et de coller le code dans le haut de votre programme. L'appeler, et elle renvoie une valeur BOOLÉENNE (true ou false).

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

Si vous avez un problème de compilation avec "__int64", remplacer "long". Il compile bien sous VS2008 et VS2010.

Comment il fonctionne:
Il ya trois parties à la fonction. La partie contrôle pour voir si c'est une des rares exceptions (les nombres négatifs, 1), et intercepte l'exécution du programme.

La deuxième partie commence si le nombre est plus petit que 1373653, qui est théoriquement numéro de Rabin-Miller algorithme va battre mon optimisé la force brute de la fonction. Puis vient deux niveaux de Rabin-Miller, conçu pour réduire le nombre de témoins nécessaires. Comme la plupart des numéros que vous allez tester sont de moins de 4 milliards de dollars, la probabiliste de Rabin-Miller algorithme peut être fait déterministe en cochant les témoins 2, 7 et 61. Si vous avez besoin d'aller sur les 4 milliards de bouchon, vous aurez besoin d'un grand nombre de la bibliothèque, et d'appliquer un module ou de décalage de bits de modification de l'alimentation() fonction.

Si vous insistez sur la force brute de la méthode, ici, c'est juste mon optimisé force brute IsPrime() fonction:

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

Comment cette force brute morceau:
Tous les nombres premiers (à l'exception des 2 et 3) peut être exprimée sous la forme 6k+1 ou 6k-1, où k est un nombre entier positif. Ce code utilise ce fait, et les tests de tous les nombres de la forme 6k+1 ou 6k-1 inférieur à la racine carrée du nombre en question. Cette pièce est intégré dans ma plus grande IsPrime() fonction (la fonction apparaît en premier).

Si vous avez besoin de trouver tous les nombres premiers ci-dessous un certain nombre, de trouver tous les nombres premiers en dessous de 1000, regarder dans le Crible d'Eratosthène. Un autre de mes préférés.

Comme une note complémentaire, je serais ravi de voir quelqu'un mettre en œuvre les Vélos Méthode de la Courbe de l'algorithme, envie de voir que implémenté en C++ pour un certain temps maintenant, j'ai perdu ma mise en œuvre. En théorie, il est même plus rapide que le déterministe Rabin-Miller algorithme j'ai mis en place, bien que je ne suis pas sûr si c'est vrai pour les nombres de moins de 4 milliards de dollars.

OriginalL'auteur LostInTheCode

Si vous connaissez la plage des entrées (dont vous avez fait depuis votre fonction prend un int), vous pouvez précalculer une table de nombres premiers inférieur ou égal à la racine carrée de l'entrée max (2^31-1 dans ce cas), puis de tester pour la divisibilité par chaque premier dans le tableau inférieur ou égal à la racine carrée du nombre donné.

OriginalL'auteur user470379

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;

OriginalL'auteur un33k

Si vous êtes paresseux, et beaucoup de RAM, créer un crible d'Eratosthène qui est pratiquement un tableau géant à partir de laquelle vous coups de pied tous les nombres qui ne sont pas le premier.
À partir de là, chaque premier "probabilité" test sera super rapide.
La limite supérieure de cette solution pour des résultats rapides est la quantité de vous RAM. La limite supérieure de cette solution pour superslow résultats de votre disque dur de capacité.

OriginalL'auteur karatedog

Utiliser les mathématiques d'abord trouver la racine carrée d'un nombre, puis démarrer en boucle jusqu'à ce que le numéro se termine que vous obtenez après l'carrés d'enracinement.
vérifier, pour chaque valeur, si le nombre donné est divisible par l'itération de la valeur .si aucune valeur divise le nombre donné, alors il n'est pas un nombre premier sinon le premier.
Voici le 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;
} 

OriginalL'auteur Dev Kumar

Il y a plusieurs manières d'aborder ce problème.

Le "Naïf" de la Méthode: Essayez-les tous (impair) les nombres jusqu'à (la racine de) le nombre.

Amélioration de la "Naïve" de la Méthode: n'essayer chaque 6n ± 1.

Probabiliste tests: de Miller-Rabin, Solovay-Strasse, etc.

L'approche qui vous convient dépend de ce que vous faites avec le premier.

Vous devriez au moins lire sur Les Tests De Primalité.

OriginalL'auteur Sani Singh Huttunen

Si n est 2, c'est le premier.

Si n est de 1, ce n'est pas le premier.

Si n est pair, il n'est pas premier.

Si n est impair, plus grand que 2, il faut vérifier tous les nombres impairs 3..sqrt(n)+1, si l'un de ces numéros peut diviser n, n n'est pas premier, d'ailleurs, n est premier.

Pour de meilleures performances, je recommande crible d'eratosthène.

Voici l'exemple de code:

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

OriginalL'auteur izanbf1803

Je suis venu avec cette:

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

OriginalL'auteur Mr. Frank

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

OriginalL'auteur Frazar Ngosa

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

Le code est incroyablement faux. 33 divisé par 2 est 16 avec rappel de 1, mais ce n'est pas un nombre premier...

OriginalL'auteur Jojo Jkee