Müssen wir den Algorithmus oder nur das Endergebnis beibehalten?
John Dvorak
Ich würde ich bei 2 beginnen, um genau zu sein, da dies 0 und 1 druckt.
Histokrat
Versuchen Sie, die Ausführung des Codes zu beschleunigen, oder versuchen Sie, weniger Zeichen im Quellcode zu verwenden?
user3629249
1
Da Sie um Unterstützung beim Golfspielen bitten, wäre es hilfreich, die Anzahl der Zeichen Ihrer aktuellen Lösung in Ihren Beitrag aufzunehmen (ich mache es als 89).
Mark Reed
Antworten:
7
59 57 Bytes
Basierend auf der @ feersum-Lösung kann die Primalitätsprüfung jedoch weiter ausgeführt werden
(Ich habe dies geschrieben, ohne die Größenbeschränkungen für Ganzzahlen in C zu berücksichtigen, daher ist es wahrscheinlich nicht wirklich nützlich, um den Code zu verkürzen.)
Zunächst ein Wort zum Algorithmus. Bevor Sie Ihren Code spielen, sollten Sie über die beste Gesamtstrategie nachdenken, um das Ergebnis zu erzielen.
Sie überprüfen die Primalität, indem Sie eine Testteilung durchführen - indem Sie jeden potenziellen Teiler pvon testen i. Das ist in Zeichen teuer, weil es zwei Schleifen braucht. Wenn Sie also die Primalität ohne Schleife testen, werden wahrscheinlich Zeichen gespeichert.
Ein oft kürzerer Ansatz ist die Verwendung von Wilsons Theorem : Die Zahl nist genau dann eine Primzahl, wenn
fact(n-1)%n == n-1
Wo factist die Fakultätsfunktion? Da Sie alles Mögliche nvon 1bis testen 1000, können Sie die Implementierung von Fakultäten leicht vermeiden, indem Sie das laufende Produkt verfolgen Pund es P*=nnach jeder Schleife aktualisieren . Hier ist eine Python-Implementierung dieser Strategie zum Drucken von Primzahlen bis zu einer Million.
Alternativ eröffnet die Tatsache, dass Ihr Programm nur bis zu 1000 sein muss, eine andere Strategie: den Fermat-Primalitätstest . Für einige aist jede Primzahl nzufriedenstellend
pow(a,n-1)%n == 1
Leider bestehen einige Verbundwerkstoffe ndiesen Test auch für einige a. Diese werden Fermat-Pseudoprimes genannt . Aber, a=2und a=3scheitern Sie erst zusammen n=1105, damit sie ausreichen, um Primzahlen bis 1000 zu überprüfen. (Wenn 1000 statt 100 wären, könnten Sie nur verwenden a=2.) Also überprüfen wir die Primalität mit (ungolfed code)
pow(2,n-1)%n == 1 and pow(3,n-1)%n == 1
Dies erkennt auch die Primzahlen 2 und 3 nicht, so dass diese in speziellen Fällen angeordnet werden müssten.
Sind diese Ansätze kürzer? Ich weiß es nicht, weil ich in C nicht codiere. Aber es sind Ideen, die Sie ausprobieren sollten, bevor Sie sich für einen Code entscheiden, um Zeichen zu finden.
Wilsons Satz ist in C nicht nützlich, da ints 32-Bit sind. Gleiches gilt für Fermat's.
Feersum
@feersum Oh, schieß. Das ist auch für die Fakultäten ein Problem. Gibt es einen Big-Int-Typ?
xnor
@xnor Nicht eingebaut.
Martin Ender
1
Wenn man definiert, fact(int n, int m) { return (n==0) ? 1 : (n*f(n-1)) % m; }wird das Ergebnis eine 32-Bit-Ganzzahl auch für ziemlich große Werte von nicht überlaufen n. ( mist der Modul)
Apnorton
@ Anorton Ich denke du meinst (n*fact(n-1,m)) % m. Was das Problem hervorhebt: Sie können die Rekursion bei der Implementierung von factweil nicht vermeiden, da msie für jede Iteration der äußeren Schleife unterschiedlich ist.
HD
4
78 77 Zeichen
(Habe gerade einige Tricks angewendet, die in anderen Sprachen gelernt wurden.)
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);}
Antworten:
5957 BytesBasierend auf der @ feersum-Lösung kann die Primalitätsprüfung jedoch weiter ausgeführt werden
Bearbeitet basierend auf den Kommentaren von Runer112
quelle
d=p++%999
. Ansonsten sieht das ziemlich luftdicht aus!67 Bytes
In C gibt es keine wirkliche Alternative zur Testabteilung, aber es kann sicherlich ein bisschen Golf gespielt werden.
Erfordert C99-Erstdeklarationen, wodurch 1 Byte eingespart wird.
quelle
(Ich habe dies geschrieben, ohne die Größenbeschränkungen für Ganzzahlen in C zu berücksichtigen, daher ist es wahrscheinlich nicht wirklich nützlich, um den Code zu verkürzen.)
Zunächst ein Wort zum Algorithmus. Bevor Sie Ihren Code spielen, sollten Sie über die beste Gesamtstrategie nachdenken, um das Ergebnis zu erzielen.
Sie überprüfen die Primalität, indem Sie eine Testteilung durchführen - indem Sie jeden potenziellen Teiler
p
von testeni
. Das ist in Zeichen teuer, weil es zwei Schleifen braucht. Wenn Sie also die Primalität ohne Schleife testen, werden wahrscheinlich Zeichen gespeichert.Ein oft kürzerer Ansatz ist die Verwendung von Wilsons Theorem : Die Zahl
n
ist genau dann eine Primzahl, wennWo
fact
ist die Fakultätsfunktion? Da Sie alles Möglichen
von1
bis testen1000
, können Sie die Implementierung von Fakultäten leicht vermeiden, indem Sie das laufende Produkt verfolgenP
und esP*=n
nach jeder Schleife aktualisieren . Hier ist eine Python-Implementierung dieser Strategie zum Drucken von Primzahlen bis zu einer Million.Alternativ eröffnet die Tatsache, dass Ihr Programm nur bis zu 1000 sein muss, eine andere Strategie: den Fermat-Primalitätstest . Für einige
a
ist jede Primzahln
zufriedenstellendLeider bestehen einige Verbundwerkstoffe
n
diesen Test auch für einigea
. Diese werden Fermat-Pseudoprimes genannt . Aber,a=2
unda=3
scheitern Sie erst zusammenn=1105
, damit sie ausreichen, um Primzahlen bis 1000 zu überprüfen. (Wenn 1000 statt 100 wären, könnten Sie nur verwendena=2
.) Also überprüfen wir die Primalität mit (ungolfed code)Dies erkennt auch die Primzahlen 2 und 3 nicht, so dass diese in speziellen Fällen angeordnet werden müssten.
Sind diese Ansätze kürzer? Ich weiß es nicht, weil ich in C nicht codiere. Aber es sind Ideen, die Sie ausprobieren sollten, bevor Sie sich für einen Code entscheiden, um Zeichen zu finden.
quelle
int
s 32-Bit sind. Gleiches gilt für Fermat's.fact(int n, int m) { return (n==0) ? 1 : (n*f(n-1)) % m; }
wird das Ergebnis eine 32-Bit-Ganzzahl auch für ziemlich große Werte von nicht überlaufenn
. (m
ist der Modul)(n*fact(n-1,m)) % m
. Was das Problem hervorhebt: Sie können die Rekursion bei der Implementierung vonfact
weil nicht vermeiden, dam
sie für jede Iteration der äußeren Schleife unterschiedlich ist.7877 Zeichen(Habe gerade einige Tricks angewendet, die in anderen Sprachen gelernt wurden.)
76 Zeichen im C99-Modus
quelle
58 Zeichen (oder 61 für ein vollständiges Programm)
Eine weitere Wiederverwendung meiner Antwort auf eine ähnliche Frage .
BEARBEITEN : eigenständiges Codeteil, keine aufzurufende Funktion.
Komplettes Programm:
quelle
6764 BytesInspiriert von Alchymists Lösung:
quelle