Alle Primzahlen von 0 bis 1000

9

Ist es möglich, diesen C-Code zu verkleinern? Es werden alle Primzahlen von 0 bis 1000 ausgedruckt.

C 89 Zeichen

int i,p,c;for(i=2;i<1e3;i++){c=0;for(p=2;p<i;p++)if(i%p==0)c++;if(c==0)printf("%u\n",i);}
Jonas Grunau
quelle
6
Nur um einigen Downvotes "Wir wollen keine sprachspezifischen Herausforderungen" vorzubeugen, ist es ein Thema und eine andere Geschichte als Herausforderungen , um Hilfe beim Golfen von Code zu bitten .
Martin Ender
4
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

for(int p=1,d;d=p++%999;d||printf("%d\n",p))for(;p%d--;);

Bearbeitet basierend auf den Kommentaren von Runer112

Alchymist
quelle
2
Der gebundene Scheck kann etwas mehr gespielt werden : d=p++%999. Ansonsten sieht das ziemlich luftdicht aus!
Runer112
10

67 Bytes

In C gibt es keine wirkliche Alternative zur Testabteilung, aber es kann sicherlich ein bisschen Golf gespielt werden.

for(int p=1,d;p++<999;d&&printf("%d\n",p))for(d=p;--d>1;)d=p%d?d:1;

Erfordert C99-Erstdeklarationen, wodurch 1 Byte eingespart wird.

Feersum
quelle
6

(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.

xnor
quelle
1
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);}

76 Zeichen im C99-Modus

for(int i=0,p,c;i<1e3;i++){c=0;for(p=2;p<i;)c+=i%p++<1;c||printf("%u\n",i);}
Mann bei der Arbeit
quelle
2

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.

for(int m,n=2;n<999;m>1?m=n%m--?m:n++:printf("%d\n",m=n));

Komplettes Programm:

n=2;main(m){n<999&&main(m<2?printf("%d\n",n),n:n%m?m-1:n++);}
ugoren
quelle
1

67 64 Bytes

Inspiriert von Alchymists Lösung:

int i=1,p;for(;i++<1e3;p-i||printf("%d\n",i)){p=1;while(i%++p);}
Sahil Arora
quelle