Wszystkie liczby pierwsze od 0 do 1000


9

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);}

6
Po to, aby uprzedzić niektóre komentarze „Nie chcemy konkretnych wyzwań językowych”, proszenie o pomoc w odszukaniu kodu jest tematem i inną historią niż wyzwania.
Martin Ender,

4
Czy musimy zachować algorytm, czy tylko wynik końcowy?
John Dvorak,

Chciałbym zacząć od 2, żeby być ściśle dokładne, ponieważ drukuje 0 i 1.
histokrata

próbujesz przyspieszyć wykonanie kodu, czy próbujesz użyć mniejszej liczby znaków w kodzie źródłowym?
user3629249,

1
Ponieważ prosisz o pomoc w golfie, pomocne byłoby umieszczenie liczby postów w twoim aktualnym rozwiązaniu (postaram się, aby było to 89).
Mark Reed,

Odpowiedzi:


7

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


2
Związany check można golfed nieco więcej: d=p++%999. W przeciwnym razie wygląda to dość szczelnie w golfa!
Runer112,

10

67 bajtów

W C nie ma realnej alternatywy dla próbnego podziału, ale z pewnością można trochę pograć w golfa.

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

Wymaga wstępnych deklaracji C99, co pozwala zaoszczędzić 1 bajt.


6

(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 pz 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 njest liczbą pierwszą wtedy i tylko wtedy

fact(n-1)%n == n-1

gdzie factjest funkcja silnia. Ponieważ testujesz wszystkie możliwe nod 1do 1000, łatwo jest uniknąć implementacji silni, śledząc działający produkt Pi aktualizując go P*=npo 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 akażda liczba pierwsza nspełnia

pow(a,n-1)%n == 1

Niestety niektóre kompozyty nrównież zdają ten test a. Są to tak zwane pseudopierwsze Fermata . Ale a=2i a=3nie zawiedźcie razem, dopóki n=1105wię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.


1
Twierdzenie Wilsona nie jest przydatne w C, ponieważ ints są 32-bitowe. To samo dotyczy Fermata.
feersum

@feersum Och, strzelaj. To także problem dla silni. Czy istnieje typ big-int?
xnor

@xnor Nie wbudowane.
Martin Ender,

1
jeśli zdefiniujemy, 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. ( mjest modułem)
apnorton

@anorton Myślę, że masz na myśli (n*fact(n-1,m)) % m. Co podkreśla problem: nie można uniknąć rekurencji w implementacji, factponieważ mbędzie różna dla każdej iteracji zewnętrznej pętli.
hvd

4

78 77 znaków

(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);}

76 znaków w trybie C99

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);}

2

58 znaków (lub 61 dla kompletnego programu)

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++);}

1

67 64 bajtów

Zainspirowany rozwiązaniem Alchymist:

int i=1,p;for(;i++<1e3;p-i||printf("%d\n",i)){p=1;while(i%++p);}
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.