Qui est l'algorithme le plus rapide pour trouver les nombres premiers?

Qui est l'algorithme le plus rapide pour trouver les nombres premiers en utilisant le C++? J'ai utilisé le tamis de l'algorithme, mais j'en veux encore être plus rapide!

Un vieil article que j'ai trouvé, mais semble intéressant: Amusant Avec les Nombres premiers
Je pense que le plus facile & plus rapide façon de vérifier si un nombre est ou non premier: c'est par convertir un nombre binaire en nombre, et de vérifier ensuite si ses extrêmes 1 et dans le milieu sont de 0 tels que 1,101,1001,..
cette échoue pour des chiffres aussi bas que 7 (111). Il échoue également pour 1001=9. Et de toute évidence, elle échoue pour presque tous les nombres premiers en général (ce qui n'est pas le cas 2^p - 1, qui sont des nombres premiers de Mersenne - classique généré exemples - qui sera toujours de la forme 111...1)
Il y a un regex pour que
Hahahaha tu m'as donné une bonne tranche de rire il y a @Hot Licks
Vous n'avez pas mentionné qui Tamis? Tu veux sans doute dire Tamis de Eranthoses!

InformationsquelleAutor kasperasky | 2009-01-17

algorithm c++primes

73

Une très rapide mise en œuvre de la Crible d'Atkin est Dan Bernstein primegen. Ce tamis est plus efficace que la Crible d'Eratosthène. Sa page a certaines informations de référence.
- En fait, je ne pense pas que primegen est le plus rapide, ou même la deuxième plus forte; yafu et primesieve sont à la fois plus rapide en général, je pense, et certainement plus de 2^32. Les deux sont (modifié) tamis d'Eratosthène plutôt que de la Atkin-Bernstein tamis.
- Primesieve Crible d'Eratosthène (SoE) est le plus rapide de l'algorithme possible et sera toujours plus rapide que toute mise en œuvre du Crible d'Atkin SoA, y compris Bernstein comme lié à cette réponse parce que primesieve réduit le nombre d'opérations par rapport à SoA: Pour le nombre de 32 bits (2^32 - 1), primesieve est d'environ 1,2 milliard de pertes alors que la SoA fait un total d'environ 1,4 milliard de dollars combinée à bascule et place des opérations, des opérations, de la même complexité et de pouvoir être optimisé dans près de la même manière.
- Suite: Bernstein seulement par rapport à la SoE à l'aide de la même roue de la factorisation comme pour la SoA, qui est un 2;3;5 roue, dont l'utilisation de la roue résultats dans environ 1,83 milliard de dollars les pertes sur le nombre de 32 bits gamme, ce qui rend la SoA environ 30% plus rapide lorsque l'on compare cette version restreinte de SoE équivalent pour d'autres optimisations. Cependant, la primesieve algorithme utilise une 2;3;5;7 roue en combinaison avec un 2;3;5;7;11;13;17 roue segment pré-abattage pour réduire le nombre d'opérations à environ 1,2 milliards de dollars pour exécuter environ 16,7% plus rapide que la SoA avec l'équivalent fonctionnement de la boucle d'optimisations.
- Continued2: La SoA con de ne pas avoir plus de facteur de roue factorisation utilisé pour faire beaucoup de différence, car les 2;3;5 factorisation de la roue est un "cuit-dans la seconde partie de l'algorithme.
- si wikipédia est de le croire, la atkin tamis a une (très) légèrement mieux complexité de calcul par un facteur log log N bien sûr, c'est si petit, qu'il ne va pas beaucoup plus que le générique de réglage.
- Nerbonne, WP est correct; cependant, avoir juste un peu plus de complexité de calcul ne prend pas en faire un des algorithmes plus rapides pour une utilisation générale. Dans ces commentaires, je me réfère au maximum de la roue de la factorisation du Crible d'Eratosthène (SoE) (qui n'est pas possible pour le Crible d'Atkin - SoA) fait pour un peu moins d'opérations pour le SoE jusqu'à une distance d'environ un milliard de dollars. Bien au-dessus de ce point, on a généralement besoin d'utiliser la page de segmentation pour surmonter les limitations de la mémoire, et c'est là que la SoA ne parvient pas, en prenant rapidement des quantités croissantes de frais généraux constants avec l'augmentation de la gamme.
- Q. est-ce que quelqu'un a une idée de comment utiliser le Crible d'Atkin en appelant un natif en Java? en d'autres termes, je voudrais pont de la bibliothèque écrite en C à partir de Java à l'aide natif plutôt que de ré-écrire en Java?
InformationsquelleAutor Greg Hewgill
27

Si elle doit être vraiment rapide, vous pouvez inclure une liste de nombres premiers:

http://www.bigprimes.net/archive/prime/

Si vous avez juste à savoir si un nombre est un nombre premier, il y a diverses premier essais listés sur wikipédia. Ils sont probablement la méthode la plus rapide pour déterminer si les grands nombres sont premiers, en particulier parce qu'ils peuvent vous dire si un nombre est pas un premier.
- Une liste de tous les nombres premiers? Je pense que tu veux dire une liste des premiers nombres premiers... 🙂
- Si vous appelez 100000000 un peu, alors oui. 🙂
- sûrement 100000000 est "un peu", les comparant à l'infini 😉
- Pourquoi pensez-vous que le Crible d'Atkin (SoA) est plus rapide que le Crible d'Eratosthène (SoE)? Il n'est certainement pas quand on seulement met en œuvre un programme à l'aide de la pseudo-code, comme dans l'article de Wikipedia est lié. Si le SoE est mis en œuvre avec un niveau similaire d'optimisations possibles que sont utilisés avec la SoA, alors il y a un peu moins d'opérations que pour les très grandes tamisage des plages pour les SoA que pour SoE, mais ce gain est généralement plus que compensée par l'augmentation de la complexité et de l'extra constante facteur de charge de cette complexité de calcul, tels que pour les applications pratiques, le SoE est mieux.
InformationsquelleAutor Georg Schölly
25

Lui, lui, je sais que je suis une question nécromancien répondre à de vieilles questions, mais je viens de trouver cette question de la recherche sur le net pour les moyens à mettre en œuvre efficace des nombres premiers tests.

Jusqu'à maintenant, je crois que la manière la plus rapide de nombre premier algorithme de dépistage est Fort Probable Premier (SPRP). Je cite à partir de Nvidia CUDA forums:

L'un des plus pratique de niche problèmes en théorie des nombres a faire
avec l'identification de nombres premiers. Étant donné N, comment pouvez-vous efficacement
déterminer s'il est premier ou pas? Ce n'est pas seulement un thoeretical
problème, il peut être un réel besoin dans le code, peut-être quand vous en avez besoin pour
trouver dynamiquement un premier table de hachage de taille au sein de certaines plages. Si N
une chose est sur l'ordre de 2^30, voulez-vous vraiment faire 30000
la division des tests pour rechercher les facteurs? Évidemment pas.

La commune de solution pratique à ce problème est un simple test appelé
une Euler probable premier essai, et un plus puissant généralisation
appelé Fort Probable Premier (SPRP). Ceci est un test que pour un
entier N peut de manière probabiliste la classer en tant que premier ou non, et
des essais répétés peuvent augmenter la probabilité de l'exactitude. La partie lente
le test en lui-même implique la plupart du temps de calcul d'une valeur similaire à
A^(N-1) modulo N. Quiconque la mise en œuvre du RSA à clé publique de chiffrement
variantes a utilisé cet algorithme. Il est utile à la fois pour les grands entiers
(comme 512 bits) ainsi que normale 32 ou 64 bits ints.

Le test peut être modifié à partir d'un probabiliste de rejet dans un
la preuve définitive de la primalité par precomputing certains test d'entrée
les paramètres qui sont connus pour toujours réussir pour des gammes de N.
Malheureusement, la découverte de ces "meilleurs tests connus" est effectivement
a la recherche d'une énorme (en fait infinie) de domaine. En 1980, une première liste de
utile tests a été créé par Carl Pomerance (célèbre pour être l'un
pour le facteur de RSA-129 avec son Quadratique Seive algorithme.) Plus Tard Jaeschke
amélioré significativement les résultats en 1993. En 2004, Zhang et Tang
l'amélioration de la théorie et de la limite du domaine de recherche. Greathouse et
Livingstone, qui ont publié le plus moderne des résultats jusqu'à présent sur les
web, à http://math.crg4.com/primes.html, les meilleurs résultats d'un énorme
domaine de recherche.

Voir ici pour plus d'info:
http://primes.utm.edu/prove/prove2_3.html et http://forums.nvidia.com/index.php?showtopic=70483

Si vous avez juste besoin d'un moyen de produire de très grands nombres premiers et ne se soucient pas de générer tous les nombres premiers < un entier n, vous pouvez utiliser de Lucas-Lehmer de test pour vérifier les nombres premiers de Mersenne. Un nombre de Mersenne premier numéro est de la forme 2^p -1. Je pense que Lucas-Lehmer test est l'algorithme le plus rapide découvert pour les nombres premiers de Mersenne.

Et si vous ne voulez seulement utiliser l'algorithme le plus rapide mais aussi le plus rapide du matériel, essayez de la mettre en œuvre à l'aide de Nvidia CUDA, écrire un noyau pour CUDA et l'exécuter sur GPU.

Vous pouvez même gagner de l'argent si vous découvrez un assez grand nombres premiers, le FEP est de donner un prix à partir de $50 à $250K:
https://www.eff.org/awards/coop

InformationsquelleAutor Mack
16

Il est 100% mathématique de test qui permet de vérifier si un certain nombre P est premier ou composé, appelé AKS Test de Primalité.

Le concept est simple: étant donné un nombre P, si tous les coefficients de (x-1)^P - (x^P-1) sont divisibles par P, puis P est un nombre premier, sinon c'est un nombre composé.

Par exemple, étant donné P = 3, donnerait le polynôme:
```
   (x-1)^3 - (x^3 - 1)
 = x^3 + 3x^2 - 3x - 1 - (x^3 - 1)
 = 3x^2 - 3x
```
Et les coefficients sont tous les deux divisibles par 3, donc le nombre est premier.

Et exemple où P = 4, qui n'est PAS le premier donnerait:
```
   (x-1)^4 - (x^4-1)
 = x^4 - 4x^3 + 6x^2 - 4x + 1 - (x^4 - 1)
 = -4x^3 + 6x^2 - 4x
```
Et ici, nous pouvons voir que les coefficients 6 n'est pas divisible par 4, par conséquent, il n'est PAS premier.

Le polynôme (x-1)^P sera P+1 conditions et peut être trouvé à l'aide de la combinaison. Donc, ce test sera exécuté dans O(n) de l'exécution, donc je ne sais pas comment utile ce serait puisque vous pouvez simplement effectuer une itération sur i de 0 à p et de test pour le reste.
- AKS est un processus très lent de la méthode dans la pratique, pas en concurrence avec d'autres méthodes connues. La méthode que vous décrivez n'est pas AKS, mais une ouverture lemme qui est plus lent que unoptimized section de première instance (comme vous le soulignez).
- bonjour @Kousha, ce qui ne l' x signifie? dans (x-1)^P - (x^P-1). avez-vous un exemple de code pour cela? en C++ permettant de déterminer si un entier est premier ou pas?
- X est juste une variable. C'est le coefficient de X que de déterminer si le nombre est premier ou pas. Et non je n'ai pas le code. Je ne recommande pas d'utiliser cette méthode pour déterminer si un nombre est premier ou pas. C'est juste un très cool mathématique du comportement de nombres premiers, mais sinon il est incroyablement inefficace.
InformationsquelleAutor Kousha
5

Est votre problème afin de déterminer si un nombre est premier? Ensuite, vous avez besoin d'un test de primalité (facile). Ou avez-vous besoin de tous les nombres premiers inférieurs à un nombre donné? Dans ce cas, le premier tamis sont de bonne qualité (facile, mais nécessite de la mémoire). Ou avez-vous besoin de facteurs premiers d'un nombre? Cela nécessiterait de la factorisation (difficile pour un grand nombre, si vous voulez vraiment les méthodes les plus efficaces). De quelle taille sont les numéros que vous regardez? 16 bits? 32 bits? plus grand?

Un habile et efficace consiste à pré-calculer des tables de nombres premiers et de les conserver dans un fichier en utilisant un peu au niveau de l'encodage. Le fichier est considéré comme un long vecteur de bits tandis que les bits n représente l'entier n. Si n est premier, son bit est mis à un et zéro sinon. De recherche est très rapide (permet de calculer le décalage d'octet et un masque de bits) et ne nécessite pas de charger le fichier en mémoire.
- Un bon test de primalité est en concurrence avec la mémoire principale de latence pour le premier tables qui pourraient raisonnablement propres, je ne voudrais pas l'utiliser à moins qu'il puisse s'insérer dans L2.
InformationsquelleAutor Christian Lindig
3

Rabin-Miller est un standard de test de primalité probabiliste. (vous l'exécutez K fois et le nombre d'entrée est certainement composite, ou il est probablement le premier avec une probabilité d'erreur de 4^-K. (quelques centaines d'itérations, et c'est presque certainement vous dire la vérité)

Il y a un non-probabiliste (déterministe) variante de Rabin-Miller.

La Great Internet Mersenne Prime Search (GIMPS) qui a trouvé le record du monde pour le plus grand prouvé premier (2^74,207,281 - 1 en juin 2017), utilise plusieurs algorithmes, mais ce sont des nombres premiers dans des formes spéciales. Cependant, le GIMPS page ci-dessus ne comprennent en général les tests de primalité déterministe. Ils semblent indiquer que l'algorithme est "le plus rapide" dépend de la taille du nombre à être testé. Si votre numéro s'inscrit en 64 bits, alors vous ne devriez probablement pas utiliser une méthode conçue pour fonctionner sur les nombres premiers de plusieurs millions de chiffres.

InformationsquelleAutor Jason S
2

Cela dépend de votre application. Il ya quelques considérations:
- Faire, vous avez juste besoin de l'information indiquant si un peu de nombres sont premiers, avez-vous besoin de tous les nombres premiers jusqu'à une certaine limite, ou avez-vous besoin d' (potentiellement) tous les nombres premiers?
- Quelle sont les numéros que vous avez à traiter avec?
De Miller-Rabin et analogique tests ne sont plus rapides que d'un tamis pour les nombres sur une certaine taille (quelque part autour de quelques millions, je crois). Au-dessous, à l'aide d'une section de première instance (si vous ne disposez que de quelques numéros) ou un tamis est plus rapide.

InformationsquelleAutor Svante

Je vous laisse décider si c'est plus rapide ou pas.

using System;
namespace PrimeNumbers
{
public static class Program
{
static int primesCount = 0;
public static void Main()
{
DateTime startingTime = DateTime.Now;
RangePrime(1,1000000);   
DateTime endingTime = DateTime.Now;
TimeSpan span = endingTime - startingTime;
Console.WriteLine("span = {0}", span.TotalSeconds);
}
public static void RangePrime(int start, int end)
{
for (int i = start; i != end+1; i++)
{
bool isPrime = IsPrime(i);
if(isPrime)
{
primesCount++;
Console.WriteLine("number = {0}", i);
}
}
Console.WriteLine("primes count = {0}",primesCount);
}
public static bool IsPrime(int ToCheck)
{
if (ToCheck == 2) return true;
if (ToCheck < 2) return false;
if (IsOdd(ToCheck))
{
for (int i = 3; i <= (ToCheck / 3); i += 2)
{
if (ToCheck % i == 0) return false;
}
return true;
}
else return false; //even numbers(excluding 2) are composite
}
public static bool IsOdd(int ToCheck)
{
return ((ToCheck % 2 != 0) ? true : false);
}
}
}

Il faut environ 82 secondes pour trouver et imprimer des nombres premiers dans une plage de 1 à 1 000 000, sur mon Core 2 Duo ordinateur portable avec un 2,40 GHz de processeur. Et il a trouvé 78,498 nombres premiers.

c'est beaucoup trop lent. le problème est i <= (ToCheck / 3). il devrait être i <= (ToCheck / i). avec elle, il peut fonctionner en 0.1 secondes à la place.

InformationsquelleAutor Tayyab Mazhar

-1

J'utilise toujours cette méthode pour le calcul des nombres premiers numéros à la suite avec le tamis de l'algorithme.

void primelist()
{
for(int i = 4; i < pr; i += 2) mark[ i ] = false;
for(int i = 3; i < pr; i += 2) mark[ i ] = true; mark[ 2 ] = true;
for(int i = 3, sq = sqrt( pr ); i < sq; i += 2)
if(mark[ i ])
for(int j = i << 1; j < pr; j += i) mark[ j ] = false;
prime[ 0 ] = 2; ind = 1;
for(int i = 3; i < pr; i += 2)
if(mark[ i ]) ind++; printf("%d\n", ind);
}

InformationsquelleAutor Osman Goni Nahid

-2

Je ne sais pas à propos de tout algorithme prédéfini, mais j'ai créé mon propre qui est très rapide. Il peut traiter 20 chiffres en moins de 1 seconde. Le max de la capacité de ce programme est 18446744073709551615. Le programme est :

#include <iostream>
#include <cmath>
#include <stdlib.h>
using namespace std;
unsigned long long int num = 0;
bool prime() {
if (num % 2 == 0 || num == 1) {
return false;
}
unsigned long int square_root = sqrt(num);
for (unsigned long int i = 3; i <= square_root; i += 2) {
if (num % i == 0) {
return false;
}
}
return true;
}
int main() {
do {
system("cls");
cout << "Enter number : ";
cin >> num;
if (prime()) {
cout << "The number is a prime number" << endl << endl << endl << endl;
} else {
cout << "The number is not a prime number" << endl << endl << endl << endl;
}
system("pause");
} while (1);
return 0;
}

InformationsquelleAutor Sushant

-3

#include<stdio.h>
main()
{
long long unsigned x,y,b,z,e,r,c;
scanf("%llu",&x);
if(x<2)return 0;
scanf("%llu",&y);
if(y<x)return 0;
if(x==2)printf("|2");
if(x%2==0)x+=1;
if(y%2==0)y-=1;
for(b=x;b<=y;b+=2)
{
z=b;e=0;
for(c=2;c*c<=z;c++)
{
if(z%c==0)e++;
if(e>0)z=3;
}
if(e==0)
{
printf("|%llu",z);
r+=1;
}
}
printf("|\n%llu outputs...\n",r);
scanf("%llu",&r);
}

r est utilisé avant d'être initialisé

InformationsquelleAutor Tjandra

-4

#include <iostream>
using namespace std;
int set [1000000];
int main (){
for (int i=0; i<1000000; i++){
set [i] = 0;
}
int set_size= 1000;
set [set_size];
set [0] = 2;
set [1] = 3;
int Ps = 0;
int last = 2;
cout << 2 << " " << 3 << " ";
for (int n=1; n<10000; n++){
int t = 0;
Ps = (n%2)+1+(3*n);
for (int i=0; i==i; i++){
if (set [i] == 0) break;
if (Ps%set[i]==0){
t=1;
break;
}
}
if (t==0){
cout << Ps << " ";
set [last] = Ps;
last++;
}
}
//cout << last << endl;
cout << endl;
system ("pause");
return 0;
}

cela devrait être une réponse sur "Comment écrire du code non structurées sans utilisation de GOTO". Tout cela confuscation juste pour code une simple division de première instance! (n%2)+1+(3*n) est une sorte de gentil si. 🙂
Ness j'aurais downvoted cela comme une réponse à la question, pourquoi utiliser une boucle for lorsqu'une macro va faire? 🙂

InformationsquelleAutor vidura

-4

Je sais que c'est un peu plus tard, mais cela pourrait être utile pour les gens qui arrivent ici, à partir de recherches. De toute façon, voici une partie du code JavaScript qui s'appuie sur le fait que seuls facteurs premiers doivent être testés, de sorte que le plus tôt primes générées par le code sont ré-utilisé comme test de facteurs pour les derniers. Bien sûr, tous les même et mod 5 valeurs sont filtrés en premier. Le résultat sera dans le tableau P, et ce code peut crunch 10 millions de nombres premiers en moins de 1,5 secondes sur un i7 PC (ou 100 millions de dollars à environ 20). Réécrit en C, il devrait être très rapide.
```
var P = [1, 2], j, k, l = 3
for (k = 3 ; k < 10000000 ; k += 2)
{
loop: if (++l < 5)
{
for (j = 2 ; P[j] <= Math.sqrt(k) ; ++j)
if (k % P[j] == 0) break loop
P[P.length] = k
}
else l = 0
}
```
- Cela vous donnera beaucoup de problèmes si vous êtes de la génération d'un grand nombre de nombres premiers, et pour la comparations, de mieux utiliser les P[j]*P[j] <= k, parce que sqrt est assez lent
InformationsquelleAutor Robin Nixon
-12
```
#include<iostream>
using namespace std;
void main()
{
int num,i,j,prime;
cout<<"Enter the upper limit :";
cin>>num;
cout<<"Prime numbers till "<<num<<" are :2, ";
for(i=3;i<=num;i++)
{
prime=1;
for(j=2;j<i;j++)
{
if(i%j==0)
{
prime=0;
break;
}
}
if(prime==1)
cout<<i<<", ";
}
}
```
- c'est sur le plus lent, vous pouvez aller à ce sujet.
- C'est très lent,si la limite supérieure est permet de dire 10000000 ce code va consommer beaucoup de temps!!!
- ce code est O(N^2/log N). sans break; il serait encore plus lent, O(N^2), mais qui pourrait être considéré comme une erreur de codage déjà. l'épargne et les tests par des nombres premiers est O(N^2/(log N)^2), et des tests par les nombres premiers ci-dessous le numéro de la racine carrée de la seule, est O(N^1.5/(log N)^2).
- Peut-être un peu hyperbolique. Il pourrait facilement avoir commencé la boucle for de 1 au lieu de 2, et a ajouté un j<=i au lieu de j<i. 🙂
- Je ne pense pas que ce poste doit être supprimé, il constitue un précieux contre-exemple.
- qui il suffit de casser le code si. mais oui, depuis que j'ai vu beaucoup plus lent codes, par exemple [n | n<-[2..], notElem(n) [j*k | j<-[2..(n-1)], k<-[2..(n-1)]]], ou le vainqueur absolu, let { isPrime(n) = n>1 && []==[i | i<-[2..n-1], isPrime(i) && rem(n)(i)==0] } in filter(isPrime) [2..] (en Haskell, désolé; l'aide de la liste de compréhension de la syntaxe; rem est pour le reste, %; [] est la liste vide). Par rapport à ces deux, l'un ici, c'est tout droit (et par la manière, équivalente à la précédente, si l'on crucial - et simple - le changement est fait).
- nice haha, j'ai aussi le code en Haskell afin que je puisse le lire. 🙂
InformationsquelleAutor Gaurav

Vous devez vous connecter pour publier un commentaire.