Un peu de pairage

20

(Inspiré au hasard par /mathpro//q/339890 )
(Connexes: 1 , 2 )

Étant donné une liste d'entrée de nombres premiers distincts (par exemple, [2, 5, 7]) et un entier n, sortez tous les entiers positifs strictement inférieurs à ceux nqui ne contiennent que ces nombres premiers comme diviseurs. Pour l' entrée [2, 5, 7]et n=15cela signifie une sortie [2, 4, 5, 7, 8, 10, 14].

Autres exemples

[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]

Règles et clarifications

  • La liste d'entrée est garantie non vide, mais peut être un seul élément
  • Vous pouvez supposer que la liste d'entrée est pré-triée de la manière la plus pratique
  • n sera toujours plus grand que le plus grand élément de la liste d'entrée
  • Depuis, par exemple, 2**0 = 1vous pouvez éventuellement inclure 1dans votre liste de sortie
  • L'entrée et la sortie peuvent être fournies par n'importe quelle méthode pratique
  • Vous pouvez imprimer le résultat dans STDOUT ou le renvoyer comme résultat de fonction
  • Un programme complet ou une fonction sont acceptables
  • Le cas échéant, vous pouvez supposer que les entiers d'entrée / sortie correspondent à la intplage native de votre langue
  • Les failles standard sont interdites
  • Il s'agit de donc toutes les règles de golf habituelles s'appliquent et le code le plus court (en octets) gagne
AdmBorkBork
la source
Pouvons-nous produire dans n'importe quel ordre?
xnor
@xnor Oui, la sortie dans n'importe quel ordre est correcte.
AdmBorkBork
Excusez-moi. Juste pour être absolument sûr: "qui ne contiennent que ces nombres premiers comme diviseurs" signifie "qui ne contient qu'au moins un de ces nombres premiers comme diviseurs premiers"?
AZTECCO
Vous devriez avoir informé les solutions existantes de la modification de la spécification à autoriser 1dans la sortie.
Shaggy
@AZTECCO C'est vrai. Mais, par exemple, si votre liste est que [2, 3, 7]vous ne pouvez pas utiliser 5.
AdmBorkBork

Réponses:

5

05AB1E , 6 octets

<LʒfåP

Prend l'entier comme première entrée, la liste comme deuxième. Inclut l'option 1en sortie.

Essayez-le en ligne ou vérifiez tous les cas de test .

Explication:

<       # 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)

Deux alternatives de 6 octets fournies par @Grimy :

GNfåP

Essayez-le en ligne.

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

Celui-ci est très lent (le [2,5,7], 15cas de test expire déjà), mais moins comme les deux autres approches:

sиPÑʒ›

Contrairement aux deux autres programmes ci-dessus, il prend la liste comme première entrée et un entier comme deuxième. 1Cependant, il inclut également l'option en option .

Essayez-le en ligne.

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
la source
1
Alternative 7: sиPѦʒ›. Je pensais avoir un 6, mais il ne semble pas y avoir moyen d'utiliser s/ I/¹
Grimmy
@Grimy Belle alternative, mais cela prend certainement beaucoup de temps à exécuter. Pour le premier cas de test, il doit trouver tous les diviseurs de 4747561509943000000000000000. ;)
Kevin Cruijssen
1
Pour la sortie verticale:GNfåP–
Grimmy
4

JavaScript (ES6),  64 ... 52  50 octets

Prend l'entrée comme (n)(primes)où les nombres premiers sont un ensemble. Sorties en modifiant l'ensemble.

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

Essayez-le en ligne!

Commenté

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
la source
4

Python 3 , 68 65 octets

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]

Essayez-le en ligne!

-3 octets grâce à @xnor

La fonction prend une séquence principale et un entier n comme entrées. La sortie est une liste qui comprend 1.

Non golfé:

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)

Essayez-le en ligne!

Joel
la source
C'est un bon code de court-circuit que vous avez. Il semble que vous puissiez combiner les deux premières conditions comme c*s<n*s. Edit: n//c*sest plus court.
xnor
@xnor Merci pour l'amélioration. Votre approche est également très bonne.
Joel
3

Haskell , 51 octets

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

np(#p)n

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

Essayez-le en ligne!

flawr
la source
3

Haskell , 39 octets

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

Essayez-le en ligne!

Vérifie si kest divisible uniquement par les nombres premiers en lvoyant si le produit de lpris à une puissance élevée est divisible par k.

xnor
la source
3

Python 2 , 65 octets

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

Essayez-le en ligne!

Vérifie si kest divisible uniquement par les nombres premiers en lvoyant si le produit de lpris à une puissance élevée est divisible par k.

Si lpeut être considéré comme une liste de chaînes eval("*".join(l)) enregistre 3 octets sur reduce(int.__mul__,l)et peut être utilisé en Python 3 qui manque reduce.

Python 3 , 64 octets

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

Essayez-le en ligne!

Une fonction les imprime dans l'ordre inverse et se termine par une erreur.

La solution récursive ci-dessous serait plus courte si nelle - même était incluse dans la liste. J'ai également essayé de calculer le produit récursivement l, mais c'était plus long.

62 octets (non fonctionnel)

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

Essayez-le en ligne!

xnor
la source
1

Gaia , 10 octets

…@e⟪ḍ‡⁻!⟫⁇

Essayez-le en ligne!

Je ne l'ai jamais utilisé avec une monade auparavant, c'est très utile pour la manipulation de la pile.

…		| 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
la source
1

Gelée , 7 octets

ṖÆffƑ¥Ƈ

Essayez-le en ligne!

Un lien dyadique prenant la limite supérieure exclusive comme argument de gauche et la liste des nombres premiers comme droite. Renvoie une liste qui comprend 1 ainsi que les nombres composés uniquement des nombres premiers fournis.

Une alternative 7 serait ṖÆfḟ¥Ðḟ

Nick Kennedy
la source
0

Japt -f , 7 octets

©k e!øV

Essayez-le

Incarnation de l'ignorance
la source
Cela inclut 1dans la sortie, ce qui ne devrait pas être le cas. J'ai aussi commencé avec k e!øVma solution mais j'avais besoin des 2 octets supplémentaires pour filtrer 0& 1.
Shaggy
Since, e.g., 2**0 = 1, you can optionally include 1 in your output list
Incarnation de l'ignorance
Cela ne faisait pas partie de la spécification d'origine.
Shaggy
0

Rubis -rprime , 61 octets

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

Essayez-le en ligne!

Encre de valeur
la source
0

Retina 0.8.2 , 64 octets

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

Essayez-le en ligne! La liste inclut des cas de test plus petits ( 10000expire à cause de toutes les longues chaînes). Prend la saisie dans l'ordre n f1 f2 f3...(les facteurs n'ont pas besoin d'être premiers mais doivent être coprimes). La sortie comprend 1. Explication:

\d+
$*

Convertissez en unaire.

\G1
$.`,$`;

Générez une liste de 0 à n-1, à la fois décimale et unaire.

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

Divisez à plusieurs reprises l'unaire par tous les facteurs disponibles.

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

Affiche les nombres décimaux où le nombre unaire a été réduit 1.

Neil
la source
0

Pyth , 10 octets

f!-PThQtUe

Essayez-le en ligne!

Prend l'entrée comme [[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
la source
0

Fusain , 22 20 octets

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

Essayez-le en ligne! Le lien est vers la version détaillée du code. Trop lent pour le cas de test plus grand. Explication:

 Φ                      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

Réponse précédente plus rapide de 22 octets:

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

Essayez-le en ligne! Le lien est vers la version détaillée du code. La sortie comprend 1. Explication:

⊞υ¹

Poussez 1vers la liste vide prédéfinie.

Fυ

Parcourez la liste, y compris tous les éléments qui y sont poussés pendant la boucle.

F×ιθ

Multipliez l'élément actuel par chaque amorçage et boucle sur les produits.

F›‹κη№υκ

Vérifiez si le produit est une nouvelle valeur.

⊞υκ

Si oui, poussez-le dans la liste.

Iυ

Imprimez la liste.

Neil
la source
0

C (clang) , 115 octets

#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];}

Essayez-le en ligne!

Une solution à base de tamis d'Ératosthène.

(Comprend 1 dans la sortie)

Merci à la suggestion de @ceilingcat: printf (x [i] + "\ 0% d", i ++) au lieu de x [i] && printf ("% d", i), i ++ je suppose que cela déplace le pointeur du littéral mais didn 'ai trouvé aucune documentation, si quelqu'un peut me donner un aperçu, ce serait la bienvenue.

AZTECCO
la source
Merci mais .. comment ça marche?
AZTECCO
1
Si x[i]==1alors la chaîne est "%d ". Si x[i]==0alors la chaîne est "". Les chaînes C sont terminées par un caractère nul, donc un caractère nul explicite termine la chaîne. Ce hack abuse également de certains comportements indéfinis en clang liés à la i++.
plafond le