Rozważ naturalną sekwencję do 6 (pomiń 1) :
2,3,4,5,6
Rozpoczynamy skanowanie od lewej (w tym przypadku od 2), szukamy liczby podzielnej przez 2 (tutaj 4), a następnie usuwamy obie liczby z listy (tutaj 2 i 4), tak że lista zmniejsza się do:
3,5,6
Kontynuujemy ten sam proces, tutaj najbardziej na lewo jest 3, więc szukamy liczby podzielnej przez 3. 6 to z pewnością ta liczba, a zatem 3 i 6 są usuwane,
5
Teraz nie można już przeprowadzać takich poszukiwań. Staje się to więc listą ZAWARTYCH liczb dla n = 6.
CEL
- Biorąc pod uwagę liczbę n większą niż 1, wydrukuj wszystkie odpowiadające sobie numery.
WKŁAD
2
6
15
20
22
WYDAJNOŚĆ
2
5
8,9,11,12,13,15
11,12,13,15,17,19,20
12,13,15,17,19,20,21
JESZCZE INNY WYKONANY PRZYKŁAD
Dla n = 22
=>2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22
=>3,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22 (remove 2 & 4)
=>5,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22 (remove 3 & 6)
=>7,8,9,11,12,13,14,15,16,17,18,19,20,21,22 (remove 5 & 10)
=>8,9,11,12,13,15,16,17,18,19,20,21,22 (remove 7 & 14)
=>9,11,12,13,15,17,18,19,20,21,22 (remove 8 & 16)
=>11,12,13,15,17,19,20,21,22 (remove 9 & 18)
=>12,13,15,17,19,20,21 (remove 11 & 22) (OUTPUT)
To jest golf golfowy , więc wygrywa najkrótszy kod w bajtach.
Odpowiedzi:
05AB1E ,
22171514 bajtówWypróbuj online!
Wyjaśnienie
źródło
Python 2,
907973 bajtów-6 bajtów dzięki xnor
Pobiera numer wejścia na standardowe wejście. Ideone to!
Wyjaśnienie
Pierwszą listę konstruujemy na podstawie numeru wejściowego i przechowujemy w niej
L
. Następnie zapętl się, gdy ostatnia liczba jest większa lub równa 2-krotności pierwszej liczby i usuń 2-krotnie pierwszą liczbę z listy. Będzie to zawsze następna liczba podzielna przezL[0]
.L=L[1:]
zdejmuje również pierwszy numer. Gdy warunek nie jest już spełniony, nie można wykonać żadnych dalszych operacji usuwania, a lista jest drukowana.źródło
range
już podaje listę.Python, 61 bajtów
Nieco łatwiej zrozumieć ten mniej golfowy kod:
Wykorzystuje to bezpośrednią charakterystykę numerów w aloncie:
Dlaczego tak się dzieje? Podczas wykonywania procesu
n
powiedzmy, że usuwamy liczbę nieparzystąa
w dolnej połowie (1
don/2
). Następnie2*a
jest usuwany bez względu na to, gdzie jest na liście.4*a
Pozostaje więc (jeśli istniał). Ale jeśli jest w dolnej połowie, proces usuwania dojdzie do niego i usunie oba4*a
i8*a
. Tak więc widzimy, że liczba górna połowa zostanie usunięty, jeśli to formy2*a
,8*a
... z dziwnec
, ale pozostaje, jeśli ma postaća
,4*a
,8*a
, ...Wyjątkiem jest
a=1
, który nie zaczyna się na liście i dlatego nie jest usuwany. W rezultacie łańcuch usuwania zaczyna się oda=2
, a zasada dla potęg 2 jest odwrócona.W powyższym kodzie
(i&-i)**.5%1>0
sprawdza, czyi
brakuje formyi = a * 2^b
zb
nieparzystym, za pomocą sztuczki bitowej w celu wyodrębnienia największego współczynnika potęgi dwóch2^b = i&-i
, a następnie sprawdza, czy wynik nie jest idealnym kwadratem. Następniei&~-i>0
jest kolejna sztuczka, aby sprawdzić, czyi
nie jest to doskonała potęga 2. Te warunki są następnie xor'owane.Tutaj jest kilka ulepszeń
Po pierwsze, przesuwamy indeks zakresu 1 w dół, aby skrócić do
range(n/2,n)
zrange(n/2+1,n+1)
, kompensując zastępując wszystkoi
przezi+1
(lub~-i
).To, czy potęga 2 jest liczbą, jest potęgą
4
(2 ^b
zb
parzystą), można sprawdzić przez i2**c/3
dla niektórych dużychc
. Jest tak, ponieważ2**c/3
ma reprezentację binarną10101...101
z bitami w parzystych pozycjach. Używaniec=2*n
wystarcza. Aby zanegować wynik, gdyi
jest potęgą 2, zmniejszamy tę liczbę o połowę, stawiając1
zamiast tego nieparzyste pozycje.źródło
Groovy,
6558 bajtówPomysł algorytmu od DSLoc , który zauważył, że wystarczy usunąć podwójne.
Oto podział:
źródło
Perl,
53494544 bajtówObejmuje +1 dla
-n
Podaj numer wejściowy na STDIN:
aloned.pl
:Bezpośrednie sprawdzanie możliwych numerów jest dłuższe:
To sprawdza wszystkie liczby w górnej połowie zakresu. Zachowaj liczby, które mają parzystą liczbę 2 jako czynniki pierwsze, z wyjątkiem sytuacji, gdy liczba jest potęgą 2, a następnie nieparzysta (ponieważ 1 jest pominięty w pierwotnej serii). Ta metoda powinna jednak działać dobrze w przypadku innych języków.
źródło
MATL , 18 bajtów
Zapożyczono pomysł „pomnóż przez 2” z odpowiedzi @ Emigna 05AB1E .
Wypróbuj online!
Wyjaśnienie
źródło
Haskell,
71696256 bajtówPrzykład użycia:
q 22
->[12,13,15,17,19,20,21]
.Jeśli jest wielokrotność pierwszego numeru
a
, to jest2*a
. Zachowaj,a
jeśli2*a
nie ma jej na liście, dołącz połączenie rekurencyjnea
i2*a
usuń je z listy.źródło
Pyth - 19 bajtów
Na pewno będzie refaktoryzacja.
Pakiet testowy .
źródło
Ruby, 124
Porównując wyniki z innymi odpowiedziami, jest to oczywiście niewłaściwe podejście:
Nieco sprytny bit polega na
a[g[0]]=a[g[1]]=!g[1]
tym, że w razie potrzeby ustawia wartości skrótu na true / false.źródło
PHP, 98 bajtów
8 bajtów oszczędzanych przez @Titus Dziękujemy
Jeśli dozwolony jest przecinek końcowy, można go skrócić o 9 bajtów
(!$a?:print"$a,");
zamiast(!$a?:print$x?",$a":$x=$a);
źródło
$a
i$b
nawiasy nie są potrzebne? Niegodziwy!(!$a?:print"$a,")
->print$a?"$a,":""
. -2 bajty dla obu wersji, jeśli użyjesz podkreślenia jako separatora.foreach(... as$v)
,$v-2
zamiast$k
i$v*2-2
zamiast$k*2+2
.$a=&$r[$k]&&$b=&$r[$k*2+2]
jak Twój komentarz działa$a=$r[$k]and$b=$r[$k*2+2]
. Przykro mi, że nie znalazłem strony wyjaśniającej kombinacje z referencjami i&&
operatorem. Ale potrzebuję referencji, a nie zadań. Nie jestem pewien, czy dozwolony jest przecinek końcowy lub inny separator.&
bitowe i odniesienia mają wyższy priorytet niż&&
operatorJavaScript, 149 bajtów
Oto działający przykład. Wszystkie funkcje HTML i wrapper () są po prostu interaktywne.
Pokaż fragment kodu
Ten niestosowany fragment kodu ma kilka komentarzy i pozwala interaktywnie zobaczyć kroki dla każdego podanego wejścia.
Pokaż fragment kodu
źródło
JavaScript (ES6), 92 bajty
Myślałem, że opublikowałem to wczoraj, ale oczywiście nie ...
Oto kolejna wersja:
źródło
Java 7, 210 bajtów
Można zdecydowanie zagrać w golfa, stosując inne podejście, prawdopodobnie używając tablicy z kilkoma sztuczkami. Ze względu na obsadę, break, listę typów i if-check jest nieco dłuższy niż oczekiwano, ale działa.
Kod niepoznany i testowy:
Wypróbuj tutaj.
Wydajność:
źródło
Rakieta 191 bajtów
Ungolfed (komentarze po ';'):
Testowanie:
Wydajność:
źródło