Das ist eine Primzahl ... fast

30

Wenn Sie jemals im Matheunterricht etwas über Primzahlen gelernt haben, müssen Sie wahrscheinlich irgendwann feststellen, ob eine Zahl eine Primzahl ist. Sie haben es wahrscheinlich vermasselt, als Sie sie noch lernten, zum Beispiel 39 für eine Primzahl zu halten. Keine Sorge, 39 ist ein Semiprime, dh es ist das Produkt zweier Primzahlen.

In ähnlicher Weise können wir eine k- fast Primzahl als das Produkt von k Primzahlen definieren. Zum Beispiel ist 40 die 4. 4-fast-Primzahl; 40 = 5 * 2 * 2 * 2, das Produkt von 4 Faktoren.

Ihre Aufgabe ist es, ein Programm / Funktion zu schreiben , die zwei ganze Zahlen akzeptiert n und k als Eingabe und Ausgabe / Rück die n - te k -fast Primzahl. Dies ist ein Code-Golf, also gewinnt das kürzeste Programm in Bytes.

Testfälle

n, k => output
n, 1 => the nth prime number
1, 1 => 2
3, 1 => 5
1, 2 => 4
3, 2 => 9
5, 3 => 27

Sonstiges

Sie müssen die Primzahlen mit anderen Mitteln als mit einer einfachen geschlossenen Form selbst generieren, wenn eine solche geschlossene Form existiert.

Conor O'Brien
quelle
Überprüfen Sie Ihre Mathematik in Ihrem ersten Beispiel: 40 ist nicht gleich 5 * 2 * 2 * 2 * 2.
GamrCorps
@GamrCorps Ah, ja, danke.
Conor O'Brien
Wie definieren Sie die n - te k-fast-Primzahl? Was bestimmt, in welcher Reihenfolge sich die k-fast-Primzahlen befinden?
GamrCorps
3
Ich glaube nicht , Ihren Ausdruck für fin Bezug auf die f[n,1]richtige ist, da die Listen von fast-Primzahlen enthalten ungerade Zahlen (zB die letzten beiden Beispiele, die als Produkt aus einer Zweierpotenz nicht ausdrückbar sind und bester). (Und es sagt auch das f[n,1] == 2*f[n,1].)
2012rcampion
1
Warum ist ein einfaches geschlossenes Formular verboten?
CalculatorFeline

Antworten:

5

Brachylog , 9 Bytes

@Sundar schlagen, indem halb so viele Bytes verwendet werden

{~l~ḋ}ᶠ⁽t

Erläuterung

                    --  Input like [n,k]
{    }ᶠ⁽            --      Find the first n values which
   ~ḋ               --          have a prime decomposition
 ~l                 --          of length k
        t           --      and take the last one

Probieren Sie es online!

Kroppeb
quelle
4

Pyke (Festschreiben 29), 8 Bytes (nicht konkurrenzfähig)

.fPlQq)e

Erläuterung:

         - autoassign Q = eval_or_not(input())
.f    )  - First eval_or_not(input) of (^ for i in range(inf))
  P      -    prime_factors(i)
   l     -   len(^)
     q   -  ^==V
    Q    -   Q
       e - ^[-1]
Blau
quelle
4

Julia, 84 78 59 57 Bytes

f(n,k,i=1)=n>0?f(n-(sum(values(factor(i)))==k),k,i+1):i-1

Dies ist eine rekursive Funktion, die zwei Ganzzahlen akzeptiert und eine Ganzzahl zurückgibt. Der Ansatz besteht hier darin, die Summe der Exponenten in der Primfaktorisierung gegen zu prüfen k.

Ungolfed:

function f(n, k, i=1)
    # We initialize a counter i as a function argument.

    # Recurse while we've encountered fewer than n k-almost primes
    if n > 0
        # If the sum of the exponents in the prime factorization of i is
        # equal to k, there are k prime factors of i. We subtract a boolean
        # from n, which is implicitly cast to an integer, which will
        # decrement n if i is k-almost prime and leave it as is otherwise.
        return f(n - (sum(values(factor(i))) == k), k, i + 1)
    else
        # Otherwise we return i-1 (i will have been incremented one too
        # many times, hence the -1)
        return i - 1
    end
end
Alex A.
quelle
4

Gelee, 9 Bytes

ÆfL=³
ç#Ṫ

Probieren Sie es online!

Wie es funktioniert

Ç#Ṫ    Main link. Left input: k. Right input: n.

Ç      Apply the helper link to k, k + 1, k + 2, ... until...
 #       n matches are found.
  Ṫ    Retrieve the last match.


ÆfL=³  Helper link. Left argument: k (iterator)

Æf     Yield the prime factors of k.
  L    Compute the length of the list, i.e., the number of prime factors.
   =³  Compare the result with k (left input).
Dennis
quelle
1
Mir ist keine Codierung bekannt, mit der diese 9 Zeichen als 9 Byte gespeichert werden können.
Oleh Prypin
1
Jelly verwendet eine benutzerdefinierte Codierung , die die 256 Zeichen darstellt, die es mit einzelnen Bytes versteht.
Dennis
3

Brachylog , 18 Bytes

,1{hH&t<NḋlH;N}ⁱ⁽t

Probieren Sie es online!

                      Implicit input, say [5, 3]
,1                    Append 1 to the input list. [5, 3, 1]
  {           }ⁱ⁽     Repeat this predicate the number of times given by
                        the first element of the list (5),
                        on the rest of the list [3, 1]
   hH&                Let's call the first element H
      t<N             There is a number N greater than the second element
         ḋ            Whose prime factorization's
          l           length
           H          is equal to H
            ;N        Then, pair that N with H and let that be input for
                      the next iteration
                 t    At the end of iterations, take the last N
                      This is implicitly the output
Sundar - Setzen Sie Monica wieder ein
quelle
1

Mathematica, 56 51 Bytes

Last@Select[Range[2^##],PrimeOmega@#==n&/.n->#2,#]&

Warnung: Dies ist theoretisch. Laufen Sie nicht für Werte> 4. Ersetzen Sie 2 ^ ## durch einen effizienteren Ausdruck.

CalculatorFeline
quelle
Das funktioniert nicht für n=1.
IPoiler
Auch da PrimeOmega[1]auswertet 0, &&#>1ist überflüssig.
IPoiler
1

Mathematica, 53 49 Bytes

Cases[Range[2^(#2+#)],x_/;PrimeOmega@x==#2][[#]]&

Erzeugt eine Liste von Ganzzahlen basierend auf einer losen Obergrenze. PrimeOmegazählt die Primfaktoren mit Multiplizitäten, die k- fast Primzahl Caseswird aus der Liste genommen und das n- te Mitglied dieser Teilmenge wird zurückgegeben.

IPoiler
quelle
2 ^ (0 + ##) oder nur 2 ^ ## funktioniert.
CalculatorFeline
@CatsAreFluffy Versuchen Sie herauszufinden 2^Sequence[1,2], warum letzteres fehlschlägt.
IPoiler
1

Haskell, 88 Bytes

Kann wahrscheinlich noch viel mehr golfen werden, da ich noch ein Neuling bei Haskell bin. Die Funktion qgibt die Anzahl der Faktoren ihres Arguments zurück und fverwendet diese, um das nthElement einer Liste zu erhalten, die aus allen Zahlen mit kFaktoren besteht.

q n|n<2=0|1>0=1+q(div n ([x|x<-[2..],mod n x<1]!!0))
f n k=filter(\m->q m==k)[1..]!!n-1
Fehler
quelle
1

MATL, 14 Bytes

:YqiZ^!XpSu1G)

Probieren Sie es auf MATL Online aus

:               % Take first input n implicitly, make range 1 to n
 Yq             % Get corresponding prime numbers (1st prime to nth prime)
   i            % Take the second input k
    Z^          % Take the k-th cartesian power of the primes list 
                % (Getting all combinations of k primes)
      !Xp       % Multiply each combination (2*2*2, 2*2*3, 2*2*5, ...)
         Su     % Sort and unique
           1G)  % Take the n-th element of the result
Sundar - Setzen Sie Monica wieder ein
quelle
0

Python 3, 100 Bytes

Dies ist eine sehr einfache Brute-Force-Funktion. Es prüft jede Zahl ab 2 mit sympyder factorintFunktion 's , bis es n kfast Primzahlen gefunden hat. An diesem Punkt gibt die Funktion die nth dieser zurück.

import sympy
def a(n,k):
 z=1;c=0
 while c<n:z+=1;c+=(sum(sympy.factorint(z).values())==k)
 return z

Ungolfed:

Ich benutze, sum(factorint(a).values())weil factorintein Wörterbuch von factor: exponentPaaren zurückgibt . Wenn ich die Werte des Wörterbuchs (die Exponenten) nehme und summiere, erfahre ich, wie viele Primfaktoren es gibt und was kdiese kfast Primzahl ist.

from sympy import factorint
def almost(n, k):
    z = 1
    count = 0
    while count < n: 
        z += 1
        if sum(factorint(a).values()) == k:
            count += 1
    return z
Sherlock9
quelle
0

Python 2 , 76 Bytes

f=lambda n,k,p=2,c=0:c==k if p>n else f(n,k,p+1,c)if n%p else f(n/p,k,p,c+1)

Probieren Sie es online!

Chas Brown
quelle