Suivant la belle tradition de questions telles que Trouver le plus grand nombre premier dont la longueur, la somme et le produit sont premiers , ceci est une variante d'un plus grand défi principal.
Contribution
Votre code ne doit prendre aucune entrée.
Définition
Nous disons qu'un nombre premier p
est good
si p-1
a 2
des facteurs premiers exactement distincts.
Sortie
Votre code devrait afficher la différence absolue entre de bons nombres premiers consécutifs q
etp
sorte qu'elle |q-p|
soit aussi grande que possible et que q
le plus petit nombre premier soit plus grand que p
. Vous pouvez produire n'importe quel nombre de bonnes paires et votre dernière sortie sera prise comme score.
Exemple
La séquence des 55 premiers bons premiers est https://oeis.org/A067466 .
But
Votre score est tout simplement |q-p|
pour la paire de bons nombres premiers que vous produisez.
Langues et bibliothèques
Vous pouvez utiliser n'importe quel langage ou bibliothèque que vous aimez (qui n'a pas été conçu pour ce défi) à l' exception des fonctions de bibliothèque pour le test de primalité ou la factorisation d'entiers. Cependant, à des fins de notation, je vais exécuter votre code sur ma machine, veuillez donc fournir des instructions claires sur la façon de l'exécuter sur Ubuntu.
Ma machine Les horaires seront exécutés sur ma machine. Il s'agit d'une installation standard d'Ubuntu sur un processeur à huit cœurs AMD FX-8350 de 8 Go. Cela signifie également que je dois pouvoir exécuter votre code.
Détails
- Je tuerai votre code après 2 minutes, sauf s'il commence à manquer de mémoire avant cela. Il faut donc s'assurer de sortir quelque chose avant la coupure.
- Vous ne pouvez utiliser aucune source externe de nombres premiers.
- Vous pouvez utiliser des méthodes de test probabilistes principales, bien que Mego me dise qu'avec de bonnes tables, Miller-Rabin peut tester jusqu'à 341 550 071 728 321 (ou même plus) de manière déterministe. Voir aussi http://miller-rabin.appspot.com/ .
Meilleures entrées qui vérifient tous les entiers de 1
- 756 par cat in Go
- 756 par El'endia Starman en Python
- 1932 par Adnan en C # (utilisant mono 3.2.8)
- 2640 par yeti en Python (en utilisant pypy 4.01)
- 2754 de Reto Koradi en C ++
- 3486 par Peter Taylor à Java
- 3900 par primo dans RPython (en utilisant pypy 4.01)
- 4176 par The Coder en Java
Meilleures entrées qui peuvent ignorer un grand nombre d'entiers pour trouver un grand écart
- 14226 par Reto Koradi en C ++
- 22596 par primo dans RPython (en utilisant pypy 4.01). Record atteint après 5 secondes!
la source
Réponses:
RPython (PyPy 4.0.1), 4032
RPython est un sous-ensemble restreint de Python, qui peut être traduit en C puis compilé à l'aide de RPython Toolchain. Son but exprimé est d'aider à la création d'interprètes de langue, mais il peut également être utilisé pour compiler des programmes simples.
Pour compiler, téléchargez la source PyPy actuelle (PyPy 4.0.1) et exécutez ce qui suit:
L'exécutable résultant sera nommé
good-primes-c
ou similaire dans le répertoire de travail actuel.Notes de mise en œuvre
Le générateur de nombres premiers
primes
est un tamis d'Ératosthène illimité, qui utilise une roue pour éviter tout multiple de 2 , 3 , 5 ou 7 . Il s'appelle également de manière récursive pour générer la prochaine valeur à utiliser pour le marquage. Je suis assez satisfait de ce générateur. Le profilage de ligne révèle que les deux lignes les plus lentes sont:donc je ne pense pas qu'il y ait beaucoup de place pour l'amélioration, à part peut-être l'utilisation d'une roue plus grande.
Pour la vérification de la «qualité», tout d'abord tous les facteurs de deux sont supprimés de n-1 , en utilisant un hack bidirectionnel pour trouver la plus grande puissance de deux qui est un diviseur
(n-1 & 1-n)
. Puisque p-1 est nécessairement pair pour tout p premier > 2 , il s'ensuit que 2 doit être l'un des facteurs premiers distincts. Ce qui reste est envoyé à lais_prime_power
fonction, qui fait ce que son nom l'indique. Vérifier si une valeur est une puissance première est "presque libre", car cela se fait simultanément avec le contrôle de primalité, avec au plus O (log p n) opérations, où p est le plus petit facteur premier de n. La division d'essai peut sembler un peu naïve, mais d'après mes tests, c'est la méthode la plus rapide pour les valeurs inférieures à 2 32 . J'économise un peu en réutilisant la roue du tamis. En particulier:en itérant sur une roue de longueur 48, le
p*p < n
chèque sera sauté des milliers de fois, au prix bas et bas de pas plus de 48 opérations modulo supplémentaires. Il saute également plus de 77% de tous les candidats, plutôt que 50% en ne prenant que des cotes.Les dernières sorties sont:
Le code est également Python valide et devrait atteindre 3588 ~ 3900 lorsqu'il est exécuté avec un interpréteur PyPy récent.
RPython (PyPy 4.0.1), 22596
Cette soumission est légèrement différente des autres publiées jusqu'à présent, en ce sens qu'elle ne vérifie pas tous les bons nombres premiers, mais effectue plutôt des sauts relativement importants. Un inconvénient de cela est que les tamis ne peuvent pas être utilisés [je me sens corrigé?] , Donc il faut se fier entièrement aux tests de primalité qui en pratique sont un peu plus lents. Il existe également un juste milieu entre le taux de croissance et le nombre de valeurs vérifiées à chaque fois. Les valeurs plus petites sont beaucoup plus rapides à vérifier, mais les valeurs plus grandes sont plus susceptibles d'avoir des écarts plus importants.
Pour apaiser les dieux mathématiques, j'ai décidé de suivre une séquence semblable à Fibonacci, ayant le prochain point de départ comme la somme des deux précédents. Si aucun nouvel enregistrement n'est trouvé après avoir vérifié 10 paires, le script passe au suivant.
Les dernières sorties sont:
Lors de la compilation, des entiers 64 bits sont utilisés, bien que l'on suppose à quelques endroits que deux entiers peuvent être ajoutés sans débordement, donc en pratique, seuls 63 sont utilisables. Après avoir atteint 62 bits significatifs, la valeur actuelle est divisée par deux deux fois, pour éviter un débordement dans le calcul. Le résultat est que le script mélange les valeurs sur la plage 2 60 - 2 62 . Le fait de ne pas dépasser la précision des nombres natifs accélère également le script lorsqu'il est interprété.
Le script PARI / GP suivant peut être utilisé pour confirmer ce résultat:
la source
Probablement 4032, tamis mixte Atkin-Bernstein et Miller-Rabin "déterministe"
Factorisation des roues et bons nombres premiers
Il est très évident qu'à l'exception de 2, 3 et 5, chaque nombre premier est coprime à 2 * 3 * 5 = 60. Il existe 16 classes d'équivalence modulo 60 qui sont coprime à 60, donc tout test de primalité n'a besoin que de vérifier celles 16 cas.
Cependant, lorsque nous recherchons de «bons» nombres premiers, nous pouvons éclaircir encore plus le troupeau. Si
gcd(x, 60) = 1
, nous constatons que dans la plupart des cas,gcd(x-1, 60)
c'est 6 ou 10. Il y a 6 valeursx
pour lesquelles il est 2:Par conséquent, nous pouvons précalculer les "bons" nombres premiers de la forme
2^a 3^b + 1
et les2^a 5^b + 1
fusionner dans le résultat d'un générateur premier qui ne considère que 10% des nombres comme des nombres premiers potentiels potentiels .Notes de mise en œuvre
Étant donné que j'avais déjà une implémentation Java du tamis Atkin-Bernstein qui utilise déjà une roue comme élément clé, il semblait naturel de supprimer les rayons inutiles et d'adapter le code. J'ai essayé à l'origine d'utiliser une architecture producteur-consommateur pour exploiter les 8 cœurs, mais la gestion de la mémoire était trop compliquée.
Pour tester si un nombre premier est un "bon" nombre premier, j'utilise un test Miller-Rabin "déterministe" (ce qui signifie vraiment un test Miller-Rabin que quelqu'un d'autre a pré-vérifié par rapport à une liste générée de manière déterministe). Cela peut certainement être réécrit pour utiliser également Atkin-Bernstein, avec une certaine mise en cache pour couvrir les plages correspondant à sqrt, cbrt, etc., mais je ne sais pas si ce serait une amélioration (car ce serait tester de nombreux nombres qui Je n'ai pas besoin de tester), c'est donc une expérience pour un autre jour.
Sur mon ordinateur assez ancien, cela fonctionne
en à peu près exactement 2 minutes, puis
à 3 h 10, 3 h 20 et 3 h 30 respectivement.
Enregistrez sous
PPCG65876.java
, compilez sousjavac PPCG65876.java
et exécutez sousjava -Xmx1G PPCG65876
.la source
isGood
contrôle.C ++, 2754 (toutes les valeurs, test de primalité de force brute)
C'est de la force brute, mais c'est un début avant que nos mathématiciens résidents ne puissent travailler avec quelque chose de plus efficace.
Je peux ajouter quelques explications supplémentaires si nécessaire, mais c'est probablement très évident d'après le code. Puisque if
p
est un nombre premier différent de 2, nous savons quep - 1
c'est pair, et l'un des deux facteurs est toujours 2. Donc, nous énumérons les nombres premiers, réduisonsp - 1
par tous les facteurs 2 et vérifions que la valeur restante est soit un nombre premier, soit que tous ses facteurs sont les mêmes facteurs premiers.Code:
Le programme imprime la différence ainsi que les deux bons nombres premiers correspondants chaque fois qu'une nouvelle différence maximale est trouvée. Exemple de sortie du test effectué sur ma machine, où la valeur signalée de 2754 est trouvée après environ 1:20 minutes:
la source
C ++, 14226 (valeurs élevées uniquement, test de Miller-Rabin)
Publier ceci séparément, car il est entièrement différent de ma solution initiale, et je ne voulais pas remplacer complètement un message qui avait obtenu un certain nombre de votes positifs.
Merci à @primo d'avoir signalé un problème avec la version originale. Il y a eu un débordement pour les grands nombres dans le test des nombres premiers.
Cela profite de certaines informations qui ont été acquises au cours de l'évolution d'autres solutions. Les principales observations sont les suivantes:
Sur cette base, la méthode employée ici est assez simple:
Résultats:
Code:
la source
PyPy-2.4.0
Python-2
Le
x
fichiers...Épisode: "Regarde maman! Pas une seule division!"
;-)
Je l'ai testé sur Debian8 avec PyPy-2.4.0 et Python2 a commencé comme:
S'il y a vraiment beaucoup de RAM, la
del L[n]
ligne peut être supprimée.Le générateur de nombres premiers de base est le suivant:
Il fait exactement ce que fait le tamis d'Ératosthène, mais dans un ordre différent.
L
est un dictionnaire mais peut être vu comme une liste (bande) de listes de nombres. Les cellules inexistantesL[n]
sont interprétées commen
n'ayant jusqu'à présent aucun diviseur premier connu.La
while
boucle effectue une décision principale ou non principale à chaque tour pendantL[n]
.S'il
L[n]
existe (identique àn in L
),P = L[n]
est une liste de diviseurs premiers distincts den
. Cen
n'est donc pas une prime.Si
L[n]
n'existe pas, aucun diviseur premier n'a été trouvé. Iln
faut donc être premier alors àP = [n]
être le diviseur connu.Voici maintenant
P
la liste des diviseurs premiers connus pour les deux cas.La
for p in P
boucle déplace chaque entrée d'P
avance de la distance de sa valeur sur la bande de nombres.C'est ainsi que les diviseurs sautent sur la bande et c'est la raison pour laquelle ces nombres sautants doivent être premiers. Les nouveaux nombres ne sont enregistrés sur la bande que par la
else
décision ci-dessus et ce sont des nombres sans diviseurs connus autres qu'eux-mêmes. Les nonprimes n'entrent jamais dans ces listesL[n]
.Les nombres premiers qui sautent sur la liste sont tous distincts car chaque nombre
n
n'est regardé qu'une seule fois et n'est ajouté que comme diviseur (sinon premier :)0
ou (si premier :)1
fois. Seuls les diviseurs premiers connus avanceront mais ne seront jamais dupliqués. Il yL[n]
aura donc toujours des diviseurs premiers distincts ou sera vide.Retour au programme supérieur pour les bons écarts premiers:
... garde les diviseurs premiers
n
dansB
quandn
on sait ne pas être premier.Si
n
est reconnu comme premier,B
contient la liste des diviseurs premiers de la boucle précédente en regardantn-1
:... donc les
len(B) == 2
moyensn - 1
ont deux diviseurs premiers distincts.g
se souvient juste du dernier bon prime vu avant le nouveau,M
est la longueur de l'écart de bon prime maximum précédent etm
la longueur de l'écart nouvellement trouvé.Fin heureuse.
la source
C #, probablement 1932
J'ai découvert que plus votre algorithme est rapide pour trouver des nombres premiers, meilleur est votre score. Je suis également assez sûr que mon algorithme n'est pas la méthode la plus optimale pour la recherche principale.
la source
Python 3, 546
... en deux minutes sur ma machine, qui je pense est nettement moins puissante que la vôtre.
Je pourrais probablement rendre cela plus efficace en optimisant pour le
x=2
cas, mais hein. Assez bien. : Pla source
p: 2, q: 3, |q-p|: 1
pour moi.Allez, probablement 756
Dommage! Je suis tellement novice que je n'ai que naïvement réutilisé de l'ancien code et je m'attendais à ce qu'il fonctionne et soit rapide! Si je réimplémentais cela et le construisais vraiment autour de bons nombres premiers, ce serait tellement plus rapide, mais hélas, j'apprends. (Je répondrai probablement à nouveau demain avec une solution entièrement reconstruite spécialement conçue.)
Utilise la concurrence, évidemment.
la source
Java, 4224 (99,29 s)
Tamis d'ératosthène très personnalisé avec avantage de BitSet
Le temps pris dépend de la limite maximale des nombres premiers qui vont être calculés.
Pour
la source
Python 3, 1464
Avec l'aide de Lembik , dont l'idée était de vérifier les deux premiers bons premiers après une puissance de deux et lorsqu'ils sont trouvés, passer immédiatement à la puissance suivante de deux. Si quelqu'un peut l'utiliser comme point de départ, n'hésitez pas. Une partie de mes résultats est ci-dessous après avoir exécuté cela dans IDLE. Le code suit.
Nous remercions primo lorsque j'ai saisi leur liste de petits nombres premiers pour ce code.
Edit: j'ai édité le code pour l'adapter aux spécifications réelles du problème (deux diviseurs premiers distincts pas exactement deux diviseurs premiers distincts), et j'ai implémenté de ne pas passer à la puissance suivante de deux jusqu'à ce que les bons nombres premiers que le programme ait trouvés aient un écart plus grand que celui des deux derniers bons nombres premiers qu'il a trouvés. Je dois également rendre hommage à Peter Taylor , car j'ai utilisé son idée que les bons nombres premiers ne pouvaient être que quelques valeurs mod 60.
Encore une fois, j'ai exécuté cela sur un ordinateur lent dans IDLE, donc les résultats peuvent être plus rapides dans quelque chose comme PyPy, mais je n'ai pas pu vérifier.
Un échantillon de mes résultats (p, q, qp, temps):
Mon code:
la source
j
par4
plutôt que2
? Et vous semblez rejeter inconditionnellement si cej-1
n'est pas un prime time une puissance de deux, où vous devriez tester si c'est une puissance prime fois une puissance de deux.Aller: Tous les entiers: 5112
good.go
:Sortie:
A titre de comparaison: peterSO max 5112 en 41.04s contre The Coder max 4176 en 51.97s.
Codeur: max | qp | 4176 q 1964330609 p 1964326433
Sortie:
la source