Faut-il conserver l'algorithme, ou seulement le résultat final?
John Dvorak
Je commencerais i à 2 pour être strictement précis, car cela
affiche
essayez-vous d'accélérer l'exécution du code ou d'essayer d'utiliser moins de caractères dans le code source?
user3629249
1
Puisque vous demandez de l'aide pour le golf, il serait utile d'inclure le nombre de caractères de votre solution actuelle dans votre message (je le fais comme 89).
Mark Reed
Réponses:
7
59 57 octets
Basé sur la solution @feersum mais le contrôle de primalité peut être approfondi
(J'ai écrit ceci sans réaliser les limitations de taille sur les entiers en C, donc ce n'est probablement pas vraiment utile pour raccourcir le code.)
Tout d'abord, un mot sur l'algorithme. Avant de jouer à votre code, vous devez réfléchir à la meilleure stratégie globale pour obtenir le résultat.
Vous vérifiez la primauté en effectuant la division d'essai - en testant chaque diviseur potentiel pde i. C'est coûteux en caractères car cela prend deux boucles. Ainsi, tester la primalité sans boucle est susceptible de sauver des caractères.
Une approche souvent plus courte consiste à utiliser le théorème de Wilson : le nombre nest premier si et seulement si
fact(n-1)%n == n-1
où factest la fonction factorielle. Puisque vous testez tout le possible nde 1à 1000, il est facile d'éviter d'implémenter le factoriel en gardant une trace du produit en cours d'exécution Pet en le mettant à jour P*=naprès chaque boucle. Voici une implémentation Python de cette stratégie pour imprimer des nombres premiers jusqu'à un million.
Alternativement, le fait que votre programme ne doive être que jusqu'à 1000 ouvre une autre stratégie: le test de primalité Fermat . Pour certains a, chaque prime nsatisfait
pow(a,n-1)%n == 1
Malheureusement, certains composites nréussissent également ce test pour certains a. Celles-ci sont appelées pseudoprimes Fermat . Mais, a=2et a=3n'échouent pas ensemble avant n=1105, ils suffisent donc pour vérifier les nombres premiers jusqu'à 1000. (Si 1000 était au lieu de 100, vous ne pourriez utiliser que a=2.) Donc, nous vérifions la primauté avec (code non golfé)
pow(2,n-1)%n == 1 and pow(3,n-1)%n == 1
Cela ne reconnaît pas non plus les nombres premiers 2 et 3, donc ceux-ci devraient être placés dans un boîtier spécial.
Ces approches sont-elles plus courtes? Je ne sais pas parce que je ne code pas en C. Mais, ce sont des idées que vous devriez essayer avant de vous installer sur un morceau de code pour commencer à sortir les personnages.
Le théorème de Wilson n'est pas utile en C car les ints sont 32 bits. Il en va de même pour Fermat.
feersum
@feersum Oh, tire. C'est aussi un problème pour les factorielles. Existe-t-il un type big-int?
xnor
@xnor Non intégré.
Martin Ender
1
si l'on définit fact(int n, int m) { return (n==0) ? 1 : (n*f(n-1)) % m; }alors le résultat ne dépassera pas un entier 32 bits pour des valeurs même assez grandes de n. ( mest le module)
apnorton
@anorton Je pense que tu veux dire (n*fact(n-1,m)) % m. Ce qui met en évidence le problème: vous ne pouvez pas éviter la récursivité dans l'implémentation de factcar msera différent pour chaque itération de la boucle externe.
hvd
4
78 77 caractères
(Je viens d'appliquer quelques astuces apprises dans d'autres langues.)
int i=0,p,c;for(;i<1e3;i++){c=0;for(p=2;p<i;)c+=i%p++<1;c||printf("%u\n",i);}
Réponses:
5957 octetsBasé sur la solution @feersum mais le contrôle de primalité peut être approfondi
Modifié sur la base des commentaires de Runer112
la source
d=p++%999. Sinon, cela semble être un travail de golf assez hermétique!67 octets
En C, il n'y a pas de véritable alternative à la division d'essai, mais elle peut certainement être un peu jouée au golf.
Nécessite des déclarations initiales C99, ce qui économise 1 octet.
la source
(J'ai écrit ceci sans réaliser les limitations de taille sur les entiers en C, donc ce n'est probablement pas vraiment utile pour raccourcir le code.)
Tout d'abord, un mot sur l'algorithme. Avant de jouer à votre code, vous devez réfléchir à la meilleure stratégie globale pour obtenir le résultat.
Vous vérifiez la primauté en effectuant la division d'essai - en testant chaque diviseur potentiel
pdei. C'est coûteux en caractères car cela prend deux boucles. Ainsi, tester la primalité sans boucle est susceptible de sauver des caractères.Une approche souvent plus courte consiste à utiliser le théorème de Wilson : le nombre
nest premier si et seulement sioù
factest la fonction factorielle. Puisque vous testez tout le possiblende1à1000, il est facile d'éviter d'implémenter le factoriel en gardant une trace du produit en cours d'exécutionPet en le mettant à jourP*=naprès chaque boucle. Voici une implémentation Python de cette stratégie pour imprimer des nombres premiers jusqu'à un million.Alternativement, le fait que votre programme ne doive être que jusqu'à 1000 ouvre une autre stratégie: le test de primalité Fermat . Pour certains
a, chaque primensatisfaitMalheureusement, certains composites
nréussissent également ce test pour certainsa. Celles-ci sont appelées pseudoprimes Fermat . Mais,a=2eta=3n'échouent pas ensemble avantn=1105, ils suffisent donc pour vérifier les nombres premiers jusqu'à 1000. (Si 1000 était au lieu de 100, vous ne pourriez utiliser quea=2.) Donc, nous vérifions la primauté avec (code non golfé)Cela ne reconnaît pas non plus les nombres premiers 2 et 3, donc ceux-ci devraient être placés dans un boîtier spécial.
Ces approches sont-elles plus courtes? Je ne sais pas parce que je ne code pas en C. Mais, ce sont des idées que vous devriez essayer avant de vous installer sur un morceau de code pour commencer à sortir les personnages.
la source
ints sont 32 bits. Il en va de même pour Fermat.fact(int n, int m) { return (n==0) ? 1 : (n*f(n-1)) % m; }alors le résultat ne dépassera pas un entier 32 bits pour des valeurs même assez grandes den. (mest le module)(n*fact(n-1,m)) % m. Ce qui met en évidence le problème: vous ne pouvez pas éviter la récursivité dans l'implémentation defactcarmsera différent pour chaque itération de la boucle externe.7877 caractères(Je viens d'appliquer quelques astuces apprises dans d'autres langues.)
76 caractères en mode C99
la source
58 caractères (ou 61 pour un programme complet)
Une autre réutilisation de ma réponse à une question similaire .
EDIT : morceau de code autonome, aucune fonction à appeler.
Programme complet:
la source
6764 octetsInspiré par la solution d'Alchymist:
la source