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.
code-golf
kolmogorov-complexity
primes
Delan Azabani
la source
la source
10^6
est encore plus court;)1e6
:-DRéponses:
Mathematica ,
1724Juste pour comparaison:
Comme indiqué dans un commentaire, j’ai omis de fournir un nombre premier par ligne; correction:
la source
Prime~Array~78498
aussi 17 :)Print/@
et terminer avec;
pour empêcher la sortie d’une longue liste deNull
correctifs, au prix de 8 caractères supplémentaires.Python 3, 46 octets
Au moment où la boucle atteint le test
k
, elle a calculé de manière itérative le facteur carréP=(k-1)!^2
. Sik
prime est alors, il n'apparaît pas dans le produit1 * 2 * ... * (k-1)
, donc ce n'est pas un facteur deP
. 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 nek=4
pas s'appeler faussement premier.Plus fortement, il découle du théorème de Wilson que quand
k
est premier,P%k
égal1
. 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 sik
prime.la source
C, 61 caractères
Presque exactement le même que celui-ci (la question est presque aussi identique).
la source
SEG-FAULT
après l'impression881
-O3
àgcc
résolu le problème!n=2;main(m){n<1e6&&main(m<2?printf("%d\n",n),n:m-++n%m);}
MATLAB
(16)(12)Malheureusement, cette sortie sur une seule ligne:
mais cela se résout par une simple matrice transposée:
et je peux couper certains caractères en utilisant la notation exponentielle (comme suggéré dans les commentaires):
la source
1e6
au lieu de1000000
aide ici aussi.'
la finBash (37 caractères)
(60 caractères)
sur mon ordinateur (2,0 GHz, 2 Go de RAM) prend 14 secondes.
la source
seq 2 1000000|factor|sed 's/[0-9]*: //g;/^.* .*$/ d'
seq 1e6|factor|awk '$0=$2*!$3'
est un peu plus court.c p
où 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?seq
etfactor
sont danscoreutils
, donc c'est légitime.sed
est également assez omniprésent.coreutils
peut être traité comme un élément intégré. Bash sans coreutils est comme C ++ sans STL.J, 21 caractères
qui peut être raccourci à
Si vous savez combien de nombres premiers sont inférieurs à 1000000.
la source
,.
, au lieu de 1 [\\ pour sauvegarder un caractère. Retirez la parenthèse inutile et utiliser la notation exponentielle:1e6
.,.i.&.(p:^:_1)1e6
Pas plus court (après avoir appliqué les suggestions de @Omar) mais j'ai trouvé l'utilisation de sous intéressante.PowerShell,
47 à44 octetsTrès lent, mais le plus court possible.
PowerShell, 123 octets
C'est beaucoup plus rapide. loin d'être optimal, mais un bon compromis entre efficacité et brièveté.
la source
Ruby 34
la source
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:
Comment ça fonctionne
liste tous les entiers positifs jusqu’à 1.000.000.
les facteurs un par un. Pour les dix premiers, le résultat est le suivant:
Finalement,
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 (1
s'il s'agit d'un facteur premier ou moins,0
sinon).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é.
la source
awk '$0=$2*!$3'
c'est génial cool!Ruby
5041la source
.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)require'prime';p Prime.take 78498
.Bash, 37 ans
Je jouerai plus au golf, si je peux ...
La plupart de ceci essaie d'analyser
factor
le format de sortie peu commode.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).
la source
factor
avant, mais là c'est juste là dans les coreutils!seq 1e6|factor|grep -oP "(?<=: )\d+$"
avec un regard perl-grep-P
active 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'-o
option 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.Python 3.x: 66 caractères
Solution plus efficace: 87 caractères
Basé sur le tamis d'Eratosthène.
la source
0
et1
. Vous pouvez résoudre ce problème en utilisant plutôtrange(2,10**6)
. En outre, je pense que laif
déclaration doit être sur une ligne distincte de la sortiefor
ou vous obtenez une erreur.Haskell, 51 ans
la source
mapM_
enmapM
, la valeur de retour ne sera pas imprimée et il s'agit de Code Golf. ;)APL, 15
Mon interprète a eu des problèmes de mémoire, mais cela fonctionne en théorie.
la source
⍪
de devant pour faire un numéro par ligne, et vous n’avez pas besoin du,
.⍳
sont les premiers entiers.1↓
laisse tomber le premier.p←
assigne à p.p∘.×p
fait une table de multiplication.p~
supprime de p tout ce qui est à droite. (,
n'est pas nécessaire, la table sePerl, 49 octets
Expression régulière kung fu :)
Version non-golfée:
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
la source
1000000
peut être écrit10**6
Julia, 11 ans
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.
la source
J (15 ou 9)
Je n'arrive pas à croire que Mathematica a battu (même s'il ne s'agit que d'
un singleavec 2 caractères)Ou:
la source
... The output format should be one number per line of output.
C'est pourquoi ma réponse commence par1[\
.gs2, 5 octets
Encodé dans CP437:
1C 29
pousse un million,11 6C
est des nombres premiers en dessous,54
est montrer des lignes.la source
GolfScript, 22/20 (20/19) octets
Au prix de la vitesse, le code peut être raccourci de deux octets:
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:
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:
Définir
A = [ 2 3 4 … 999,999 ]
et| = [ 0 1 2 … 999,999 ]
.Définir
N = A[0]
et imprimerN
.Recueillir tous les N-ième élément de
|
dansC
. Ce sont les multiples deN
.Ensemble
A = A - C
.Si
A
non vide, retournez à 2.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:
la source
NARS2000 APL, 7 caractères
la source
Golfscript
26 2524Edit (enregistré un caractère supplémentaire grâce à Peter Taylor):
Ancien code:
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:
la source
\;
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$\%!}?=},`
.,
par:x,
et\.@
avecx\
(l'espace est dû aux problèmes avec MD dans les commentaires) et supprimer*
.CJam - 11
1e6,
- tableau de 0 ... 999999{mp},
- certains nombres premiersN*
- rejoindre les nouvelles lignesla source
GolfScript, 25 (24) octets
Si le format de sortie spécifié dans la question modifiée n'est pas pris en compte, un octet peut être enregistré:
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
Des repères
Plus rapide que la division d'essai, mais plus lent que le tamis d'Eratosthenes. Voir mon autre réponse .
la source
Java, 110 octets
Utilisation de la division unaire par regex comme test de primalité.
la source
C,
9188858281807672 caractèresL'algorithme est terriblement inefficace, mais puisque nous faisons du golf-code, cela ne devrait pas avoir d'importance.
la source
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é)i
sûr d'être 0? Je pense que si vous fournissez un argument, il échouera. En outre, je pense quej
va avoir une sorte d'erreur de type. Pas sûr pourb
bien.Mathematica 25
En supposant que vous ne connaissiez pas le nombre de nombres premiers inférieurs à 10 ^ 6:
la source
J, 16 caractères
Sans l'exigence de format de sortie, cela peut être réduit à 13 caractères:
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) y
est fondamentalementfilter
, oùf
retourne un booléen pour chaque élément dey
.i.1e6
est la plage d'entiers [0,1000000), et1&p:
est une fonction booléenne qui renvoie 1 pour les nombres premiers.la source
R,
4543 caractèresPour 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.
la source
Bash (433643)
Ma tentative (pas si intelligente) consistait à utiliser facteur pour factoriser le produit.
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.
Oh bien, j'ai essayé.
la source
factor
performance optimisée bien pire que l'algorithme de division d'essai de base.C #, 70
Vous ne verrez pas grand chose ici pendant très longtemps ...
la source
double
1e6
enint
, mais celaint
est requis parRange
. (2) L'intérieurRange
doit prendre au maximum lesn-2
termes, sinon vous testerezn % n
ce qui est clairement0
. (3) Vous écrivezx%n
quand vous voulezn%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.