Liste des nombres premiers inférieurs à un million

56

C’est ma première question, très simple, et je m’excuse d’avance si j’ai enfreint les directives de la communauté.

La tâche consiste à imprimer, par ordre croissant, tous les nombres premiers inférieurs à un million. Le format de sortie doit être un nombre par ligne de sortie.

Comme avec la plupart des soumissions de codes de golf, l'objectif est de minimiser la taille du code. L'optimisation pour l'exécution est également un bonus, mais est un objectif secondaire.

Delan Azabani
la source
12
Ce n'est pas un doublon exact, mais il s'agit essentiellement d'un test de primalité, qui fait partie d'un certain nombre de questions existantes (par exemple, codegolf.stackexchange.com/questions/113 , codegolf.stackexchange.com/questions/5087 , codegolf.stackexchange. com / questions / 1977 ). FWIW, une recommandation qui n’est pas suffisamment suivie (même par les personnes qui devraient en savoir plus) consiste à proposer au préalable une question dans le meta sandbox meta.codegolf.stackexchange.com/questions/423 pour la critique et la discussion de la façon dont elle peut être utilisée. amélioré avant que les gens commencent à y répondre.
Peter Taylor
Ah, oui, je craignais que cette question ne ressemble trop à la pléthore de questions relatives aux nombres premiers déjà existantes.
Delan Azabani
2
@ GlennRanders-Pehrson Car 10^6est encore plus court;)
mercredi
1
Il y a quelques années, j'ai soumis une entrée de l'IOCCC imprimant des nombres premiers avec seulement 68 caractères en C; malheureusement, elle s'arrête bien en deçà du million, mais elle pourrait intéresser certains: computronium.org/ioccc.html
Computronium
1
@ ɐɔıʇǝɥʇuʎs Que diriez-vous de 1e6:-D
Titus

Réponses:

33

Mathematica , 17 24

Juste pour comparaison:

Prime@Range@78498

Comme indiqué dans un commentaire, j’ai omis de fournir un nombre premier par ligne; correction:

Column@Prime@Range@78498
Mr.Wizard
la source
4
Prime~Array~78498aussi 17 :)
chyanog
Serait neuf octets en mthmca, si cela devait être libéré.
Michael Stern
Cela viole la condition d'un nombre premier par ligne de sortie. Préfixer avec Print/@et terminer avec ;pour empêcher la sortie d’une longue liste de Nullcorrectifs, au prix de 8 caractères supplémentaires.
celtschk
@celtschk Je ne sais pas si j'ai manqué ou négligé cela il y a cinq ans.
Mr.Wizard
1
Eh bien, j'ai définitivement manqué que c'était il y a cinq ans :-)
celtschk
27

Python 3, 46 octets

k=P=1
while k<1e6:P%k and print(k);P*=k*k;k+=1

Au moment où la boucle atteint le test k, elle a calculé de manière itérative le facteur carré P=(k-1)!^2. Si kprime est alors, il n'apparaît pas dans le produit 1 * 2 * ... * (k-1), donc ce n'est pas un facteur de P. Mais, si c'est composite, tous ses facteurs premiers sont plus petits et donc dans le produit. La quadrature n'est en réalité nécessaire que pour ne k=4pas s'appeler faussement premier.

Plus fortement, il découle du théorème de Wilson que quand kest premier, P%kégal 1. Bien que nous ayons seulement besoin que ce soit non nul ici, il est utile en général d’ P%kêtre une variable indicatrice pour savoir si kprime.

Xnor
la source
23

C, 61 caractères

Presque exactement le même que celui-ci (la question est presque aussi identique).

n=2;main(m){n<1e6&&main(m<2?printf("%d\n",n),n:n%m?m-1:n++);}
Ugoren
la source
Vous avez obtenu SEG-FAULTaprès l'impression881
mardi
7
@Manav, vous avez peut-être compilé sans optimisations. Il repose sur un bon optimiseur, qui supprimera la récursivité.
ugoren
4
Oui, en ajoutant -O3à gccrésolu le problème!
mardi
Cette méthode est folle. J'aime cela.
Todd Lehman
2
Je peux vous faire parvenir 57 octetsn=2;main(m){n<1e6&&main(m<2?printf("%d\n",n),n:m-++n%m);}
Albert Renshaw
22

MATLAB (16) (12)

Malheureusement, cette sortie sur une seule ligne:

primes(1000000)

mais cela se résout par une simple matrice transposée:

primes(1000000)'

et je peux couper certains caractères en utilisant la notation exponentielle (comme suggéré dans les commentaires):

primes(1e6)'
MBraedley
la source
5
Utiliser 1e6au lieu de 1000000aide ici aussi.
orion
@orion Cela ferait 11 personnages
Axoren
@Axoren qui n'inclut pas 'la fin
Stan Strum
20

Bash (37 caractères)

seq 2 1e6|factor|sed 's/.*: //g;/ /d'

(60 caractères)

seq 2 1000000|factor|sed -e 's/[0-9]*: //g' -e '/^.* .*$/ d'

sur mon ordinateur (2,0 GHz, 2 Go de RAM) prend 14 secondes.

Saeedn
la source
Cela peut être amélioré pour: seq 2 1000000|factor|sed 's/[0-9]*: //g;/^.* .*$/ d'
Delan Azabani
Oui tu as raison. J'ai écrit ma commande sed propre, pas au golf: P
saeedn
3
seq 1e6|factor|awk '$0=$2*!$3'est un peu plus court.
Dennis
1
seq, factor et sed sont des programmes externes, cela peut aussi bien être c poù c est un lien symbolique vers cat et p est un fichier texte avec des nombres premiers allant jusqu’à un million ... pouvez-vous le faire avec des fonctions intégrées au shell?
Technosaurus
7
@technosaurus seqet factorsont dans coreutils, donc c'est légitime. sedest également assez omniprésent. coreutilspeut être traité comme un élément intégré. Bash sans coreutils est comme C ++ sans STL.
16

J, 21 caractères

1[\p:i.(_1 p:1000000)

qui peut être raccourci à

1[\p:i.78498

Si vous savez combien de nombres premiers sont inférieurs à 1000000.

Gareth
la source
2
En utilisant des éléments d'enfil ,., au lieu de 1 [\\ pour sauvegarder un caractère. Retirez la parenthèse inutile et utiliser la notation exponentielle: 1e6.
Omar
Je suis venu avec ceci: ,.i.&.(p:^:_1)1e6Pas plus court (après avoir appliqué les suggestions de @Omar) mais j'ai trouvé l'utilisation de sous intéressante.
kaoD
10

PowerShell, 47 à 44 octets

Très lent, mais le plus court possible.

$p=2..1e6;$p|?{$n=$_;!($p-lt$_|?{!($n%$_)})}

PowerShell, 123 octets

C'est beaucoup plus rapide. loin d'être optimal, mais un bon compromis entre efficacité et brièveté.

 $p=2..1e6;$n=0
 while(1){$p=@($p[0..$n]|?{$_})+($p[($n+1)..($p.count-1)]|?{$_%$p[$n]});$n++;if($n-ge($p.count-1)){break}}
 $p
Rynant
la source
9

Ruby 34

require'prime';p Prime.take 78498
Hauleth
la source
9

Bash, 30 octets

Étant donné que saeedn ne veut pas agir sur ma suggestion - qui est à la fois plus court et plus rapide que son approche - je pensais que je poste ma propre réponse:

seq 1e6|factor|awk '$0=$2*!$3'

Comment ça fonctionne

seq 1e6

liste tous les entiers positifs jusqu’à 1.000.000.

factor

les facteurs un par un. Pour les dix premiers, le résultat est le suivant:

1:
2: 2
3: 3
4: 2 2
5: 5
6: 2 3
7: 7
8: 2 2 2
9: 3 3
10: 2 5

Finalement,

awk '$0=$2*!$3'

change la ligne entière ( $0) en le produit du deuxième champ (le premier facteur premier) et la négation logique du troisième champ ( 1s'il s'agit d'un facteur premier ou moins, 0sinon).

Ceci remplace les lignes correspondant aux nombres premiers par le nombre lui-même et toutes les autres lignes par des zéros. Puisque awk n’imprime que les valeurs de vérité, seul le nombre premier sera imprimé.

Dennis
la source
4
awk '$0=$2*!$3'c'est génial cool!
yeti
8

Ruby 50 41

require'mathn'
p (2..1e6).select &:prime?
Cristian Lupascu
la source
2
Pas besoin .to_a, car Enumerable comprend déjà select. Vous pouvez également utiliser la notation abrégée de Symbol # to_proc pour le raccourcir davantage: p (2..1e6).select &:prime?(1 n'est pas premier)
Ventero
@Ventero merci beaucoup! Je ne connaissais pas le symbole # to_proc. Je dois faire plus attention aux raccourcis proposés par Ruby.
Cristian Lupascu
2
Version plus courte require'prime';p Prime.take 78498.
Hauleth
@ ŁukaszNiemier Génial! Je pense que c'est tellement différent que vous pouvez l'afficher séparément.
Cristian Lupascu
Bonne utilisation d'un bon vieux garçon de pays, Mathn '
DoctorHeckle
8

Bash, 37 ans

Je jouerai plus au golf, si je peux ...

La plupart de ceci essaie d'analyser factorle format de sortie peu commode.

seq 1e6|factor|grep -oP "(?<=: )\d+$"

Prend environ 5,7 secondes sur ma machine.

(Il se trouve que mon message a été le premier à figurer sur la deuxième page de réponses, alors personne ne le verra ...)

Ancienne solution

C'est plus long et plus lent (prend 10 secondes).

seq 1e6|factor|egrep ':.\S+$'|grep -oE '\S+$'

la source
2
Wow - je ne suis jamais tombé sur factoravant, mais là c'est juste là dans les coreutils!
Digital Trauma
1
Détruisez un personnage: seq 1e6|factor|grep -oP "(?<=: )\d+$"avec un regard perl-grep
Digital Trauma
@DigitalTrauma comment ça marche
1
-Pactive les expressions rationnelles de style perl. (?<=: )est une observation positive de la chaîne ":". Fondamentalement, cela indique que ":" doit précéder ce qui correspond \d+$, mais ne fait pas partie du match. L' -ooption nous donne donc un nombre correspondant après les deux points, c'est-à-dire ne donne que des nombres où il n'y a qu'un seul facteur, c'est-à-dire premier.
Digital Trauma
@DigitalTrauma ajouté
8

Python 3.x: 66 caractères

for k in range(2,10**6):
 if all(k%f for f in range(2,k)):print(k)

Solution plus efficace: 87 caractères

Basé sur le tamis d'Eratosthène.

p=[];z=range(2,10**6)
while z:f=z[0];p+=[f];z=[k for k in z if k%f]
for k in p:print(k)
dan04
la source
1
Le premier imprime par erreur 0et 1. Vous pouvez résoudre ce problème en utilisant plutôt range(2,10**6). En outre, je pense que la ifdéclaration doit être sur une ligne distincte de la sortie forou vous obtenez une erreur.
xnor
@xnor: corrigé.
dan04
8

Haskell, 51 ans

mapM print [n|n<-[2..10^6],all((>0).rem n)[2..n-1]]
pt2121
la source
Vous pouvez changer mapM_en mapM, la valeur de retour ne sera pas imprimée et il s'agit de Code Golf. ;)
Dogbert
Pourquoi y a-t-il des espaces supplémentaires après impression et en (> 0)?
fier haskeller
Belle prise! merci
pt2121
Vous pouvez remplacer 999999 par 10 ^ 6. Et veuillez mettre à jour votre nombre d'octets - 63 ne peut pas être correct.
user2845840
@ user2845840 ok merci. bonne idée!
pt2121
8

APL, 15

p~,p∘.×p←1↓⍳1e6

Mon interprète a eu des problèmes de mémoire, mais cela fonctionne en théorie.

TwiNight
la source
Comment? Pouvez-vous donner une deskription?
Rasmus Damgaard Nielsen
Vous avez besoin de devant pour faire un numéro par ligne, et vous n’avez pas besoin du ,.
Adám
@RasmusDamgaardNielsen sont les premiers entiers. 1↓laisse tomber le premier. p←assigne à p. p∘.×pfait une table de multiplication. p~supprime de p tout ce qui est à droite. ( ,n'est pas nécessaire, la table se
défile
8

Perl, 49 octets

Expression régulière kung fu :)

for(1..1E6){(1x$_)=~/^(11+?)\1+$/ or print"$_\n"}

Version non-golfée:

for(1 .. 1_000_000) { 
    (1x$_) =~ /^(11+?)\1+$/ or print "$_\n";
}

Il n'a même pas fait 10% de progrès pendant que je tape ce post!

Source pour l'expression régulière: http://montreal.pm.org/tech/neil_kandalgaonkar.shtml

Gowtham
la source
2
m'a inspiré pour écrire une version de Perl6. aussi, 1000000peut être écrit10**6
pabo
1
En outre, 1000000 peut être écrit 1E6
mob
Mis à jour ma réponse. Merci @mob
Gowtham
Always a toujours été l'une de mes expressions préférées, mais vous devez vous rappeler que cela échoue de façon spectaculaire une fois que vous obtenez des nombres plus élevés, car cela convertit d'énormes nombres en unaires. Cette expression rationnelle peut ne pas fonctionner pour trouver des nombres premiers parmi des centaines de milliers et au-delà, en fonction de la configuration de la langue (et de votre machine).
Codefun64
7

Julia, 11 ans

primes(10^6)

Il semble que les utilisateurs intégrés obtiennent des votes positifs. De plus, j'avais besoin de plus de mots pour une réponse plus longue.

gggg
la source
7

J (15 ou 9)

Je n'arrive pas à croire que Mathematica a battu (même s'il ne s'agit que d' un single avec 2 caractères)

a#~1 p:a=:i.1e6

Ou:

p:i.78498
ıʇǝɥʇuʎs
la source
1
... The output format should be one number per line of output.C'est pourquoi ma réponse commence par 1[\ .
Gareth
6

gs2, 5 octets

Encodé dans CP437:

∟)◄lT

1C 29pousse un million, 11 6Cest des nombres premiers en dessous, 54est montrer des lignes.

Lynn
la source
5

GolfScript, 22/20 (20/19) octets

n(6?,:|2>{(.p|%-.}do:n

Au prix de la vitesse, le code peut être raccourci de deux octets:

n(6?,:|2>.{|%2>-}/n*

Si le format de sortie spécifié dans la question modifiée n'est pas pris en compte (ce que font beaucoup de réponses existantes), deux octets peuvent être enregistrés dans la version rapide et un dans la version lente:

n(6?,:|2>{(.p|%-.}do
n(6?,:|2>.{|%2>-}/`

Cela imprimera un LF supplémentaire après les nombres premiers pour la version rapide et les nombres premiers comme un tableau pour la version lente.

Comment ça fonctionne

Les deux versions sont des implémentations du tamis d'Eratosthène .

La version rapide fait ce qui suit:

  1. Définir A = [ 2 3 4 … 999,999 ]et | = [ 0 1 2 … 999,999 ].

  2. Définir N = A[0]et imprimer N.

  3. Recueillir tous les N-ième élément de |dans C. Ce sont les multiples de N.

  4. Ensemble A = A - C.

  5. Si Anon vide, retournez à 2.

n(6?   # Push "\n".pop() ** 6 = 1,000,000.
,:|    # Push | = [ 0 1 2 … 999,999 ].
,2>    # Push A = [ 2 3 4 … 999,999 ].
{      #
  (    # Unshift the first element (“N”) of “A”.
  .p   # Print “N”.
  |%   # Collect every N-th element from “A” into a new array, starting with the first.
  -    # Take the set difference of “A” and the array from above.
  .    # Duplicate the set difference.
}do    # If the set difference is non-empty, repeat.
:n     # Store the empty string in “n”, so no final LF will get printed.

La version lente fonctionne de la même manière, mais au lieu de supprimer successivement les multiples du minimum de «A» (toujours premier), elle supprime les multiples de tous les entiers positifs inférieurs à 1 000 000.

Compétitivité

En l'absence de fonctions mathématiques intégrées permettant de factoriser ou de vérifier la primalité, toutes les solutions GolfScript seront très volumineuses ou très inefficaces.

Bien que loin d'être efficace, je pense avoir atteint un rapport vitesse / taille décent. Au moment de sa présentation, cette approche semble être la plus courte parmi celles qui n’utilisent aucun des éléments incorporés susmentionnés. Je dis semble parce que je ne sais pas du tout comment certaines des réponses fonctionnent ...

J'ai comparé les quatre solutions GolfScript présentées: w0lf (division d'essai), mon autre réponse (théorème de Wilson) et les deux de cette réponse. Ce sont les résultats:

Bound     | Trial division     | Sieve (slow)       | Wilson's theorem | Sieve (fast)
----------+--------------------+--------------------+------------------+----------------
1,000     | 2.47 s             | 0.06 s             | 0.03 s           | 0.03 s
10,000    | 246.06 s (4.1 m)   | 1.49 s             | 0.38 s           | 0.14 s
20,000    | 1006.83 s (16.8 m) | 5.22 s             | 1.41 s           | 0.38 s
100,000   | ~ 7 h (estimated)  | 104.65 (1.7 m)     | 35.20 s          | 5.82 s
1,000,000 | ~ 29 d (estimated) | 111136.97s (3.1 h) | 3695.92 s (1 h)  | 418.24 s (7 m)
Dennis
la source
Le tamis "lent" est-il juste un tamis d'Eratosthène?
dorukayhan
Les deux sont. La version lente est juste une implémentation terrible.
Dennis
5

NARS2000 APL, 7 caractères

⍸0π⍳1e6
La ruche
la source
3
Bienvenue dans Programming Puzzles & Code Golf!
Dennis
4

Golfscript 26 25 24

Edit (enregistré un caractère supplémentaire grâce à Peter Taylor):

10 6?,{:x,{)x\%!},,2=},`

Ancien code:

10 6?,{.,{)\.@%!},,2=*},`

Ce code n'a qu'une valeur théorique, car il est incroyablement lent et inefficace. Je pense que cela pourrait prendre des heures à courir.

Si vous souhaitez le tester, essayez par exemple uniquement les nombres premiers allant jusqu'à 100:

10 2?,{:x,{)x\%!},,2=},`
Cristian Lupascu
la source
Vous pouvez sauvegarder un personnage en le remplaçant \;par *. (Vous pouvez également obtenir beaucoup plus rapidement le nombre actuel de personnages en recherchant le premier diviseur plutôt que tous:10 6?,2>{.),2>{1$\%!}?=},`
Peter Taylor
@PeterTaylor Merci, en utilisant la multiplication, il y a une astuce très soignée.
Cristian Lupascu
Il y a encore une sauvegarde de caractère avec une variable: remplacer .,par :x,et \.@avec x\ (l'espace est dû aux problèmes avec MD dans les commentaires) et supprimer *.
Peter Taylor
@PeterTaylor bien, merci! J'ai édité mon code.
Cristian Lupascu
4

CJam - 11

1e6,{mp},N*

1e6,- tableau de 0 ... 999999
{mp},- certains nombres premiers
N*- rejoindre les nouvelles lignes

Aditsu
la source
1
CJam n'est-il pas plus récent que cette question?
Peter Taylor
@PeterTaylor oh, oui c'est le cas
aditsu
4

GolfScript, 25 (24) octets

!10 6?,2>{.(@*.)@%!},n*\;

Si le format de sortie spécifié dans la question modifiée n'est pas pris en compte, un octet peut être enregistré:

!10 6?,2>{.(@*.)@%!},`\;

Cela imprimera les nombres premiers sous forme de tableau (comme le font de nombreuses autres solutions) plutôt qu’un par ligne.

Comment ça fonctionne

L'idée générale est d'utiliser le théorème de Wilson , qui stipule que n > 1 est premier si et seulement si

                                                      (n - 1)!  = -1 (mod n)

!     # Push the logical NOT of the empty string (1). This is an accumulator.
10 6? # Push 10**6 = 1,000,000.
,2>   # Push [ 2 3 4 … 999,999 ].
{     # For each “N” in this array:
  .(  # Push “N - 1”.
  @   # Rotate the accumulator on top of the stack.
  *   # Multiply it with “N - 1”. The accumulator now hold “(N - 1)!”.
  .)  # Push “(N - 1)! + 1”
  @   # Rotate “N” on top of the stack.
  %!  # Push the logical NOT of “((N - 1)! + 1) % N”.
},    # Collect all “N” for which “((N - 1)! + 1) % N == 0” in an array.
n*    # Join that array by LF.
\;    # Discard the accumulator.

Des repères

Plus rapide que la division d'essai, mais plus lent que le tamis d'Eratosthenes. Voir mon autre réponse .

Dennis
la source
3

C, 91 88 85 82 81 80 76 72 caractères

main(i,j,b){for(;i++<1e6;b++&&printf("%d\n",i))for(j=2;j<i;)b=i%j++&&b;}

L'algorithme est terriblement inefficace, mais puisque nous faisons du golf-code, cela ne devrait pas avoir d'importance.

Gareth
la source
1
vous pouvez le raccourcir facilement: main(i,j,b){for(;i++<1e6;b++&&printf("%d\n",i))for(j=2;j<i;)b=i%j++&&b;}ou une idée de ce genre (puisque je ne l’ai pas compilé en réalité)
Ali1S232
Comment est-il isûr d'être 0? Je pense que si vous fournissez un argument, il échouera. En outre, je pense que jva avoir une sorte d'erreur de type. Pas sûr pour bbien.
Erik the Outgolfer
3

Mathematica 25

En supposant que vous ne connaissiez pas le nombre de nombres premiers inférieurs à 10 ^ 6:

Prime@Range@PrimePi[10^6]
DavidC
la source
3

J, 16 caractères

1]\(#~1&p:)i.1e6

Sans l'exigence de format de sortie, cela peut être réduit à 13 caractères:

(#~1&p:)i.1e6

1]\ prend juste le tableau de rang 1 de nombres premiers, le transforme en tableau de rang 2 et met chaque nombre premier sur sa propre ligne - et ainsi le format de sortie par défaut de l'interprète transforme la liste d'une ligne en un nombre premier par ligne.

(#~ f) yest fondamentalement filter, où fretourne un booléen pour chaque élément de y. i.1e6est la plage d'entiers [0,1000000), et 1&p:est une fonction booléenne qui renvoie 1 pour les nombres premiers.

rationalis
la source
3

R, 45 43 caractères

for(i in 2:1e6)if(sum(!i%%2:i)<2)cat(i," ")

Pour chaque nombre x compris entre 2 et 1e6, indiquez-le simplement si le nombre de x mod 2 à x égal à 0 est inférieur à 2.

planificateur
la source
Le premier nombre produit par ce code est 1, mais 1 n'est pas un nombre premier.
Sven Hohenstein
@SvenHohenstein Merci, corrigé.
Plannapus
3

Bash (433643)

Ma tentative (pas si intelligente) consistait à utiliser facteur pour factoriser le produit.

factor ${PRODUCT}

Malheureusement, avec de grands nombres, le produit est bien sûr énorme. Il a également fallu plus de 12 heures pour courir. J'ai décidé de le poster car je pensais que c'était unique.

Voici le code complet.

S'il s'agissait de nombres premiers inférieurs à six ans, ce serait raisonnable.

  factor 30

Oh bien, j'ai essayé.

Kevin Cox
la source
+1 Cette réponse est vraiment diabolique. Résultat pas tout à fait précalculé (cela permet d'économiser pas mal de caractères) et beaucoup plus terrible à calculer :) C'est très probablement aussi un exemple qui rend la factorperformance optimisée bien pire que l'algorithme de division d'essai de base.
orion
3

C #, 70

Enumerable.Range(1,1e6).Where(n=>Enumerable.Range(2,n).All(x=>x%n!=0))

Vous ne verrez pas grand chose ici pendant très longtemps ...

Ce n'est pas AL.
la source
Il y a plusieurs raisons pour lesquelles c'est faux. (1) Vous ne pouvez pas convertir implicitement de a double 1e6en int, mais cela intest requis par Range. (2) L'intérieur Rangedoit prendre au maximum les n-2termes, sinon vous testerez n % nce qui est clairement 0. (3) Vous écrivez x%nquand vous voulez n%x. Si vous corrigez ces problèmes, vous obtiendrez des résultats satisfaisants. Enumerable.Range(2,999999).Where(n=>Enumerable.Range(2,n-2).All(x=>n%x!=0))Toutefois, les résultats ne sont toujours pas affichés. l'exigence était une par ligne.
Jeppe Stig Nielsen