Itu yang utama ... hampir

30

Jika Anda pernah belajar tentang bilangan prima di kelas matematika, Anda mungkin harus, pada satu titik, menentukan apakah bilangan prima. Anda mungkin telah mengacaukan saat Anda masih mempelajarinya, misalnya, salah mengira sebagai perdana. Nah, jangan khawatir, karena 39 adalah semiprime, yaitu bahwa itu adalah produk dari dua bilangan prima.

Demikian pula, kita dapat mendefinisikan prime k- hampir sebagai produk dari bilangan k prime. Misalnya, 40 adalah 4 4-hampir prima; 40 = 5 * 2 * 2 * 2, produk dari 4 faktor.

Tugas Anda adalah untuk menulis sebuah program / fungsi yang menerima dua bilangan bulat n dan k sebagai input dan output / mengembalikan n th k -hampir bilangan prima. Ini adalah kode-golf, sehingga program terpendek dalam byte menang.

Uji kasus

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

Lain-lain

Anda harus membuat bilangan prima sendiri dengan cara apa pun selain bentuk tertutup sederhana, jika ada bentuk tertutup seperti itu.

Conor O'Brien
sumber
Periksa matematika Anda dalam contoh pertama Anda: 40 tidak sama dengan 5 * 2 * 2 * 2 * 2.
GamrCorps
@ GarrCorps Ah, ya, terima kasih.
Conor O'Brien
Bagaimana Anda mendefinisikan n -k hampir prima? Apa yang menentukan bagaimana urutan k-hampir bilangan prima?
GamrCorps
3
Saya tidak menganggap ungkapan Anda fdalam hal f[n,1]ini benar, karena daftar bilangan prima hampir berisi angka ganjil (misalnya dua contoh terakhir, yang tidak dapat diungkapkan sebagai produk dari kekuatan dua dan bilangan prima). (Dan dikatakan juga demikian f[n,1] == 2*f[n,1].)
2012rcampion
1
Mengapa formulir tertutup sederhana dilarang?
CalculatorFeline

Jawaban:

8

Pyth, 9 byte

e.fqlPZQE

Penjelasan

          - autoassign Q = eval(input())
     PZ   -      prime_factors(Z) 
    l     -     len(^)
   q   Q  -    ^ == Q
 .f     E -  first eval(input()) of (^ for Z in range(inf))
e         - ^[-1]

Coba di sini!

Atau coba test suite!

Biru
sumber
5

Brachylog , 9 byte

Mengalahkan @sundar dengan menggunakan setengah byte

{~l~ḋ}ᶠ⁽t

Penjelasan

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

Cobalah online!

Kroppeb
sumber
4

Pyke (komit 29), 8 byte (tidak kompetitif)

.fPlQq)e

Penjelasan:

         - 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]
Biru
sumber
4

Julia, 84 78 59 57 byte

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

Ini adalah fungsi rekursif yang menerima dua bilangan bulat dan mengembalikan bilangan bulat. Pendekatan di sini adalah untuk memeriksa jumlah eksponen dalam faktorisasi utama terhadap k.

Tidak Disatukan:

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.
sumber
4

Jelly, 9 byte

ÆfL=³
ç#Ṫ

Cobalah online!

Bagaimana itu bekerja

Ç#Ṫ    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
sumber
1
Saya tidak mengetahui adanya penyandian yang dapat menyimpan 9 karakter ini sebagai 9 byte.
Oleh Prypin
1
Jelly menggunakan pengodean khusus yang mewakili 256 karakter yang dimengerti dengan satu byte.
Dennis
3

Brachylog , 18 byte

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

Cobalah 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 - Pasang kembali Monica
sumber
1

Mathematica, 56 51 byte

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

Peringatan: Ini teoretis. Jangan lari untuk nilai apa pun> 4. Ganti 2 ^ ## dengan ekspresi yang lebih efisien.

CalculatorFeline
sumber
Ini tidak berhasil n=1.
IPoiler
Juga sejak PrimeOmega[1]dievaluasi menjadi 0, &&#>1adalah mubazir.
IPoiler
1

Mathematica, 53 49 Bytes

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

Menghasilkan daftar bilangan bulat berdasarkan batas atas yang longgar. PrimeOmegamenghitung faktor prima dengan multiplisitas, perdana k- hampir Casesdiambil dari daftar, dan anggota ke- n dari subset tersebut dikembalikan.

IPoiler
sumber
2 ^ (0 + ##), atau hanya 2 ^ ## berfungsi.
CalculatorFeline
@CatsAreFluffy Cobalah 2^Sequence[1,2]untuk melihat mengapa yang terakhir gagal.
IPoiler
1

Haskell, 88 byte

Mungkin bisa bermain golf lebih banyak, karena saya masih pemula di Haskell. Fungsi qmengembalikan jumlah faktor argumennya, dan fmenggunakannya untuk mengambil nthelemen daftar yang dibuat dari semua angka yang memiliki kfaktor.

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
cacat
sumber
1

MATL, 14 byte

:YqiZ^!XpSu1G)

Cobalah di MATL Online

:               % 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 - Pasang kembali Monica
sumber
0

Python 3, 100 byte

Ini adalah fungsi brute force yang sangat sederhana. Ia memeriksa setiap nomor mulai dari 2 dengan sympy's factorintfungsi sampai telah menemukan n kbilangan prima-hampir, di mana titik, fungsi mengembalikan nth ini.

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

Tidak Disatukan:

Saya menggunakan sum(factorint(a).values())karena factorintmengembalikan kamus factor: exponentberpasangan. Meraih nilai-nilai dari kamus (eksponen) dan menjumlahkan mereka memberitahu saya berapa banyak faktor prima ada dan dengan demikian apa kini kprime-hampir adalah.

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
sumber
0

Python 2 , 76 byte

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)

Cobalah online!

Chas Brown
sumber