Czy można zmniejszyć ten kod C? Drukuje wszystkie liczby pierwsze od 0 do 1000.
C, 89 znaków
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);}
Czy można zmniejszyć ten kod C? Drukuje wszystkie liczby pierwsze od 0 do 1000.
C, 89 znaków
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);}
Odpowiedzi:
59 57 bajtów
Oparty na rozwiązaniu @feersum, ale kontrola pierwszeństwa może być dalej rozgrywana w golfa
for(int p=1,d;d=p++%999;d||printf("%d\n",p))for(;p%d--;);
Edytowane na podstawie komentarzy Runer112
d=p++%999
. W przeciwnym razie wygląda to dość szczelnie w golfa!
(Napisałem to, nie zdając sobie sprawy z ograniczeń wielkości liczb całkowitych w C, więc prawdopodobnie nie jest to przydatne do skracania kodu).
Najpierw słowo o algorytmie. Przed golfem kodu powinieneś pomyśleć o najlepszej ogólnej strategii, aby uzyskać wynik.
Jesteś sprawdzanie pierwszości wykonując podział testową - testowanie każdego potencjalnego dzielnik p
z i
. Jest to kosztowne dla postaci, ponieważ wymaga dwóch pętli. Zatem testowanie pierwotności bez pętli może uratować znaki.
Często krótszym podejściem jest użycie twierdzenia Wilsona : liczba n
jest liczbą pierwszą wtedy i tylko wtedy
fact(n-1)%n == n-1
gdzie fact
jest funkcja silnia. Ponieważ testujesz wszystkie możliwe n
od 1
do 1000
, łatwo jest uniknąć implementacji silni, śledząc działający produkt P
i aktualizując go P*=n
po każdej pętli. Oto implementacja tej strategii Pythona do drukowania liczb pierwszych do miliona.
Alternatywnie, fakt, że twój program musi mieć dokładnie 1000, otwiera inną strategię: test pierwszeństwa Fermata . Dla niektórych a
każda liczba pierwsza n
spełnia
pow(a,n-1)%n == 1
Niestety niektóre kompozyty n
również zdają ten test a
. Są to tak zwane pseudopierwsze Fermata . Ale a=2
i a=3
nie zawiedźcie razem, dopóki n=1105
więc nie wystarczą do sprawdzenia liczb pierwszych do 1000. (Gdyby 1000 było 100, można by użyć tylko a=2
.) Tak więc sprawdzamy pierwotność za pomocą (kodu nie golfowego)
pow(2,n-1)%n == 1 and pow(3,n-1)%n == 1
To również nie rozpoznaje liczb pierwszych 2 i 3, więc te będą musiały być w specjalnej obudowie.
Czy te podejścia są krótsze? Nie wiem, bo nie koduję w C. Ale są to pomysły, które powinieneś wypróbować, zanim zdecydujesz się na kawałek kodu, aby zacząć odszukiwać znaki.
int
s są 32-bitowe. To samo dotyczy Fermata.
fact(int n, int m) { return (n==0) ? 1 : (n*f(n-1)) % m; }
wynik nie przepełni 32-bitowej liczby całkowitej dla nawet dość dużych wartości n
. ( m
jest modułem)
(n*fact(n-1,m)) % m
. Co podkreśla problem: nie można uniknąć rekurencji w implementacji, fact
ponieważ m
będzie różna dla każdej iteracji zewnętrznej pętli.
(Właśnie zastosowałem kilka sztuczek nauczonych w innych językach).
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);}
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);}
Kolejne ponowne użycie mojej odpowiedzi na podobne pytanie .
EDYCJA : samodzielna część kodu, brak funkcji do wywołania.
for(int m,n=2;n<999;m>1?m=n%m--?m:n++:printf("%d\n",m=n));
Kompletny program:
n=2;main(m){n<999&&main(m<2?printf("%d\n",n),n:n%m?m-1:n++);}
Zainspirowany rozwiązaniem Alchymist:
int i=1,p;for(;i++<1e3;p-i||printf("%d\n",i)){p=1;while(i%++p);}