Trochę Najwyższego Parostwa

20

(Losowo inspirowany /mathpro//q/339890 )
(Powiązane: 1 , 2 )

Biorąc pod uwagę listę wejściową różnych liczb pierwszych (np. [2, 5, 7]) I liczbę całkowitą n, wypisz wszystkie dodatnie liczby całkowite ściśle mniejsze niż te, nktóre zawierają tylko te liczby pierwsze jako dzielniki. Dla danych wejściowych, [2, 5, 7]a n=15to oznacza wartość wyjściową [2, 4, 5, 7, 8, 10, 14].

Dalsze przykłady

[list] n | output

[2, 5, 7] 15 | [2, 4, 5, 7, 8, 10, 14]
[2, 5, 7] 14 | [2, 4, 5, 7, 8, 10]
[2] 3 | [2]
[2] 9 | [2, 4, 8]
[103, 101, 97] 10000 | [97, 101, 103, 9409, 9797, 9991]
[97, 101, 103] 104 | [97, 101, 103]

Zasady i wyjaśnienia

  • Lista wejściowa jest gwarantowana jako niepusta, ale może być tylko jednym elementem
  • Możesz założyć, że lista wejściowa jest wstępnie posortowana w najbardziej dogodny sposób
  • n zawsze będzie większy niż największy element na liście danych wejściowych
  • Ponieważ np. 2**0 = 1Możesz opcjonalnie dołączyć 1do swojej listy wyników
  • Dane wejściowe i wyjściowe można podać dowolną dogodną metodą
  • Możesz wydrukować wynik do STDOUT lub zwrócić go jako wynik funkcji
  • Dopuszczalny jest pełny program lub funkcja
  • Jeśli dotyczy, możesz założyć, że liczby całkowite wejścia / wyjścia pasują do natywnego intzakresu twojego języka
  • Standardowe luki są zabronione
  • To jest więc obowiązują wszystkie zwykłe zasady gry w golfa, a wygrywa najkrótszy kod (w bajtach)
AdmBorkBork
źródło
Czy możemy produkować w dowolnej kolejności?
xnor
@ xnor Tak, wyjście w dowolnej kolejności jest w porządku.
AdmBorkBork
Przepraszam ... Żeby być absolutnie pewnym: „które zawierają tylko te liczby pierwsze jako dzielniki” oznacza „które zawierają tylko jedną z tych liczb pierwszych jako dzielniki główne”?
AZTECCO
Powinieneś był poinformować istniejące rozwiązania o zmianie specyfikacji, aby zezwolić 1na wynik.
Shaggy
@AZTECCO Prawo. Ale na przykład, jeśli twoja lista jest [2, 3, 7], nie możesz użyć 5.
AdmBorkBork

Odpowiedzi:

5

05AB1E , 6 bajtów

<LʒfåP

Pobiera liczbę całkowitą jako pierwsze wejście, a listę jako drugie. Obejmuje opcjonalne 1w danych wyjściowych.

Wypróbuj online lub sprawdź wszystkie przypadki testowe .

Wyjaśnienie:

<       # Decrease the (implicit) input by 1
 L      # Create a list in the range [1,input-1]
  ʒ     # Filter it by:
   f    #  Get all prime factors of the current number (without duplicates)
    å   #  Check for each if its in the (implicit) input-list
     P  #  And check if this is truthy for all
        # (after the filter, the result is output implicitly)

Dwie 6 bajtowe alternatywy dostarczone przez @Grimy :

GNfåP

Wypróbuj online.

G       # Loop `N` in the range [1, (implicit) input):
 Nf     #  Get all prime factors of `N` (without duplicates)
   å    #  Check for each if its in the (implicit) input-list
    P   #  And check if this is truthy for all
       #  If it is, output the current `N` with trailing newline

Ten jest bardzo wolny ( [2,5,7], 15przypadek testowy już się skończył), ale mniej niż pozostałe dwa podejścia:

sиPÑʒ›

W przeciwieństwie do pozostałych dwóch programów powyżej, lista przyjmuje jako pierwsze wejście, a liczba całkowita jako druga. Zawiera jednak również opcjonalny 1wynik.

Wypróbuj online.

s       # Swap so the stack is now [list-input, integer-input]
 и      # Repeat the list (flattened) the integer amount of times
        #  i.e. [2,5] and 10 → [2,5,2,5,2,5,2,5,2,5,2,5,2,5,2,5,2,5,2,5]
  P     # Take the product of this list
        #  → 10000000000
   Ñ    # Get all divisors of this integer
        # (the bottleneck for larger integers in this approach)
        #  → [1,2,4,5,8,10,16,20,25,32,40,50,64,80,100,125,128,160,200,250,256,320,400,500,512,625,640,800,1000,1024,1250,1280,1600,2000,2500,2560,3125,3200,4000,5000,5120,6250,6400,8000,10000,12500,12800,15625,16000,20000,25000,25600,31250,32000,40000,50000,62500,64000,78125,80000,100000,125000,128000,156250,160000,200000,250000,312500,320000,390625,400000,500000,625000,640000,781250,800000,1000000,1250000,1562500,1600000,1953125,2000000,2500000,3125000,3200000,3906250,4000000,5000000,6250000,7812500,8000000,9765625,10000000,12500000,15625000,16000000,19531250,20000000,25000000,31250000,39062500,40000000,50000000,62500000,78125000,80000000,100000000,125000000,156250000,200000000,250000000,312500000,400000000,500000000,625000000,1000000000,1250000000,2000000000,2500000000,5000000000,10000000000]
    ʒ   # Filter these divisors:
       #  And only keep those where the (implicit) input-integer is larger than the divisor
        #  → [1,2,4,5,8]
        # (after the filter, the result is output implicitly)
Kevin Cruijssen
źródło
1
Alternatywa 7: sиPѦʒ›. Myślałem, że mam 6, ale wydaje się, że nie ma sposobu na użycie s/ I/¹
Grimmy
@Grimy Fajna alternatywa, ale z pewnością wykonanie jej zajmuje dużo czasu. W pierwszym przypadku testowym musi znaleźć wszystkie dzielniki 4747561509943000000000000000. ;)
Kevin Cruijssen
1
Dla wyjścia pionowego:GNfåP–
Grimmy
4

JavaScript (ES6),  64 ... 52  50 bajtów

Zajmuje wejście jak (n)(primes)gdzie liczb pierwszych jest zbiorem. Wyjście poprzez modyfikację zestawu.

n=>g=(s,q=1)=>{for(p of s)(p*=q)<n&&g(s.add(p),p)}

Wypróbuj online!

Skomentował

n =>              // n = maximum value
g = (             // g is a recursive function taking:
  s,              //   s = set of primes
  q = 1           //   q = current product, initialized to 1
) => {            //
  for(p of s)     // for each value p in s:
    (p *= q)      //   multiply p by q
    < n &&        //   if the result is less than n:
      g(          //     do a recursive call:
        s.add(p), //       with p added to the set
        p         //       with q = p
      )           //     end of recursive call
}                 //
Arnauld
źródło
4

Python 3 , 68 65 bajtów

f=lambda s,n,c=1:n//c*s and f(s,n,s[0]*c)+f(s[1:],n,c)or[c][:c<n]

Wypróbuj online!

-3 bajty dzięki @xnor

Funkcja przyjmuje jako sekwencję pierwszą sekwencję i liczbę całkowitą n. Dane wyjściowe to lista zawierająca 1.

Nie golfowany:

def f(s, n, c=1):
    if not c < n:
       return []
    elif not s:
       return [c]
    else:
       return f(s,n,s[0]*c) + f(s[1:],n,c)

Wypróbuj online!

Joel
źródło
To dobry kod, który masz. Wygląda na to, że możesz połączyć dwa pierwsze warunki jako c*s<n*s. Edycja: n//c*sjest krótsza.
xnor
@xnor Dzięki za ulepszenie. Twoje podejście jest również całkiem dobre.
Joel
3

Haskell , 51 bajtów

xpmapM((<$>[0..n]).(^))p1,x,x2,,xnnproduct

np(#p)n

p#n=[k|k<-product<$>mapM((<$>[0..n]).(^))p,k<n,k>1]

Wypróbuj online!

wada
źródło
3

Haskell , 39 bajtów

l%n=[k|k<-[2..n-1],mod(product l^k)k<1]

Wypróbuj online!

Sprawdza, czy kmożna podzielić tylko przez liczby pierwsze l, sprawdzając, czy iloczyn lwziętej do dużej mocy jest podzielny przez k.

xnor
źródło
3

Python 2 , 65 bajtów

lambda l,n:[k for k in range(2,n)if reduce(int.__mul__,l)**n%k<1]

Wypróbuj online!

Sprawdza, czy kmożna podzielić tylko przez liczby pierwsze l, sprawdzając, czy iloczyn lwziętej do dużej mocy jest podzielny przez k.

Jeśli lmożna przyjmować w postaci listy łańcuchów eval("*".join(l)) oszczędza 3 bajty nad reduce(int.__mul__,l)i mogą być używane w Pythonie 3, który brakuje reduce.

Python 3 , 64 bajty

def f(l,n,P=1):
 for x in l:P*=x
 n-=1;P**n%n or print(n);f(l,n)

Wypróbuj online!

Funkcja drukuje w odwrotnej kolejności i kończy się z błędem.

Poniższe rozwiązanie rekurencyjne byłoby krótsze, gdyby nsamo znalazło się na liście. Próbowałem również rekurencyjnie obliczać iloczyn l, ale to było dłużej.

62 bajty (niedziałające)

f=lambda l,n:n*[f]and[n][reduce(int.__mul__,l)**n%n:]+f(l,n-1)

Wypróbuj online!

xnor
źródło
1

Gaia , 10 bajtów

…@e⟪ḍ‡⁻!⟫⁇

Wypróbuj online!

Nigdy wcześniej nie korzystałem z monady, jest to całkiem przydatne do manipulacji stosami.

…		| push [0..n-1]
@e		| push list of primes
  ⟪    ⟫⁇	| filter [0..n-1] for where the following predicate is true:
   ḍ‡		| the list of prime factors
     ⁻		| minus the list of primes
      !		| is empty
Giuseppe
źródło
1

Galaretka , 7 bajtów

ṖÆffƑ¥Ƈ

Wypróbuj online!

Diadadicowy link przyjmujący wyłączną górną granicę za lewy argument i listę liczb pierwszych za prawą. Zwraca listę zawierającą 1, a także liczby złożone tylko z podanych liczb pierwszych.

Alternatywą byłoby 7 ṖÆfḟ¥Ðḟ

Nick Kennedy
źródło
0

Japt -f , 7 bajtów

©k e!øV

Spróbuj

Wcielenie ignorancji
źródło
Obejmuje 1to dane wyjściowe, których nie powinno. Zacząłem od k e!øVdla mojego rozwiązania, ale potrzebowałem 2 dodatkowych bajtów do filtrowania 0i 1.
Shaggy
Since, e.g., 2**0 = 1, you can optionally include 1 in your output list
Embodiment of Ignorance
To nie było częścią oryginalnej specyfikacji.
Shaggy
0

Ruby -rprime , 61 bajtów

->n,l{(2..n).select{|i|i.prime_division.all?{|b,|[b]-l==[]}}}

Wypróbuj online!

Wartość tuszu
źródło
0

Retina 0.8.2 , 64 bajty

\d+
$*
\G1
$.`,$`;
+`,(1+)(\1)*(?=;.* \1\b)
,1$#2$*
!`\d+(?=,1;)

Wypróbuj online! Lista zawiera mniejsze przypadki testowe ( 10000przekroczony limit czasu z powodu wszystkich długich ciągów). Pobiera dane wejściowe w kolejności n f1 f2 f3...(czynniki nie muszą być liczbami pierwszymi, ale muszą być pierwszymi pierwszymi). Dane wyjściowe obejmują 1. Wyjaśnienie:

\d+
$*

Konwertuj na unary.

\G1
$.`,$`;

Wygeneruj listę od 0 do n-1dziesiętnych i jednoargumentowych.

+`,(1+)(\1)*(?=;.* \1\b)
,1$#2$*

Wielokrotnie podziel jedność przez dowolne dostępne czynniki.

!`\d+(?=,1;)

Podaj liczby dziesiętne, w których liczba jednoargumentowa została zredukowana do 1.

Neil
źródło
0

Pyth , 10 bajtów

f!-PThQtUe

Wypróbuj online!

Pobiera dane wejściowe jako [[primes...], n]

        Ue  # range(0, Q[-1])  (Q is the input, implicit)
       t    #                [1:] -> range(1, Q[-1]), tUe == PSe
f           # filter that on the condition: lambda T:
   PT       # prime_divisors(T)
  -  hQ     #                   - Q[0]
 !          # logical negation (![] == True)
ar4093
źródło
0

Węgiel drzewny , 22 20 bajtów

IΦ…²η⬤…·²ι∨﹪ιλ⊙θ¬﹪λν

Wypróbuj online! Link jest do pełnej wersji kodu. Zbyt wolny dla większego przypadku testowego. Wyjaśnienie:

 Φ                      Filter on
  …                     Range from
   ²                    Literal `2` to
    η                   Input limit
     ⬤                  Where all values
      …·                Inclusive range from
        ²               Literal `2` to
         ι              Filter value
          ∨             Either
             λ          Inner value
           ﹪            Is not a divisor of
            ι           Filter value
              ⊙         Or any of
               θ        Input primes
                   ν    Current prime
                ¬﹪      Is a divisor of
                  λ     Inner value
I                       Cast to string for implicit print

Poprzednia szybsza 22-bajtowa odpowiedź:

⊞υ¹FυF×ιθF›‹κη№υκ⊞υκIυ

Wypróbuj online! Link jest do pełnej wersji kodu. Dane wyjściowe obejmują 1. Wyjaśnienie:

⊞υ¹

Wciśnij 1do wstępnie zdefiniowanej pustej listy.

Fυ

Pętla nad listą, w tym wszelkie elementy wypychane do niej podczas pętli.

F×ιθ

Pomnóż bieżącą pozycję przez każdą liczbę pierwszą i zapętl produkty.

F›‹κη№υκ

Sprawdź, czy produkt jest nową wartością.

⊞υκ

Jeśli tak, to wypchnij go na listę.

Iυ

Wydrukuj listę.

Neil
źródło
0

C (brzęk) , 115 bajtów

#define f(n,l,z){int j,i,k,x[n]={};for(i=x[1]=1;i<n;printf(x[i]+"\0%d ",i++))for(j=z;j--;k<n?x[k]=x[i]:0)k=i*l[j];}

Wypróbuj online!

Rozwiązanie oparte na sicie Eratostenesa.

(Obejmuje 1 wynik)

Dzięki sugestii @ceilingcat: printf (x [i] + "\ 0% d", i ++) zamiast x [i] && printf ("% d", i), i ++ Podejrzewam, że przesuwa wskaźnik literału, ale nie zrobił nie znalazłem żadnej dokumentacji, jeśli ktoś mógłby dać mi jakieś spostrzeżenia, byłby mile widziany.

AZTECCO
źródło
Dzięki, ale ... jak to działa?
AZTECCO
1
Jeśli x[i]==1to ciąg jest "%d ". Jeśli x[i]==0to ciąg jest "". Ciągi C są zakończone znakiem NULL, więc jawny znak zerowy kończy ciąg. Ten hack narusza również niektóre niezdefiniowane zachowania w brzękach związanych z i++.
ceilingcat