Ada banyak tantangan terkait faktorisasi prima / prima baru-baru ini, jadi saya pikir mungkin menarik untuk pergi ke arah lain.

Diberikan:

• bilangan bulat positif n, dan
• daftar bilangan bulat positif yang tidak kosong f

menulis program lengkap atau fungsi untuk menemukan integer terkecil isehingga i >= ndan imerupakan produk dari elemen integer nonnegatif f.

Contoh:

• Misalkan n = 11, f = [2, 3, 5].

  Beberapa produk pertama adalah:

  1   = 2^0 * 3^0 * 5^0
  2   = 2^1 * 3^0 * 5^0
  3   = 2^0 * 3^1 * 5^0
  5   = 2^0 * 3^0 * 5^1
  4   = 2^2 * 3^0 * 5^0
  6   = 2^1 * 3^1 * 5^0
  10  = 2^1 * 3^0 * 5^1
  9   = 2^0 * 3^2 * 5^0
  15  = 2^0 * 3^1 * 5^1
  25  = 2^0 * 3^0 * 5^2
  8   = 2^3 * 3^0 * 5^0
  12  = 2^2 * 3^1 * 5^0 => smallest greater than (or equal to) 11, so we output it.
  20  = 2^2 * 3^0 * 5^1
  18  = 2^1 * 3^2 * 5^0
  30  = 2^1 * 3^1 * 5^1
  50  = 2^1 * 3^0 * 5^2
  27  = 2^0 * 3^3 * 5^0
  45  = 2^0 * 3^2 * 5^1
  75  = 2^0 * 3^1 * 5^2
  125 = 2^0 * 3^0 * 5^3
  

• Misalkan n=14, f=[9, 10, 7].

  Sekali lagi, beberapa produk pertama:

  1 = 7^0 * 9^0 * 10^0
  7 = 7^1 * 9^0 * 10^0
  9 = 7^0 * 9^1 * 10^0
  10 = 7^0 * 9^0 * 10^1
  49 = 7^2 * 9^0 * 10^0  => smallest greater than (or equal to) 14, so we output it.
  63 = 7^1 * 9^1 * 10^0
  70 = 7^1 * 9^0 * 10^1
  81 = 7^0 * 9^2 * 10^0
  90 = 7^0 * 9^1 * 10^1
  100 = 7^0 * 9^0 * 10^2
  

Kasus uji:

n, f -> output
10, [2, 3, 5]              -> 10
17, [3, 7]                 -> 21
61, [3,5,2,7]              -> 63
23, [2]                    -> 32
23, [3]                    -> 27
23, [2, 3]                 -> 24
31, [3]                    -> 81
93, [2,2,3]                -> 96
91, [2,4,6]                -> 96
1,  [2,3,5,7,11,13,17,19]  -> 1
151, [20,9,11]             -> 180
11616, [23,32]             -> 12167
11616, [23,32,2,3]         -> 11664 = 2^4 * 3^6
5050, [3,6,10,15,21,28,36,45,55,66,78,91,105,120,136,153,171,190,210] -> 5103 = 3^6 * 7
12532159, [57, 34, 12, 21] -> 14183424 = 12^5 * 57

Aturan

• Anda dapat berasumsi bahwa fakan mengandung setidaknya satu elemen, dan bahwa semua elemen fakan lebih besar dari 1.
• Anda dapat secara opsional berasumsi bahwa fdiurutkan dalam pesanan menurun / meningkat jika Anda mau (tapi tolong sebutkan)
• Anda dapat mengambil sejumlah elemen fjika Anda mau.
• Output sebagai string diizinkan.
• Ini adalah kode-golf , jadi jawaban terpendek dalam byte di setiap bahasa akan menang!
• Aturan I / O standar berlaku, dan celah standar dilarang.
• Penjelasan didorong.

Sekam , 8 byte

ḟṠ€ȯmΠṖṘ

Sangat lambat. Cobalah online!

Penjelasan

ḟṠ€ȯmΠṖṘ  Implicit inputs, say L=[3,4] and n=5.
ḟ         Find the lowest integer k≥n that satisfies:
       Ṙ   Replicate L by k: [3,3,3,3,3,4,4,4,4,4]
      Ṗ    Powerset: [[],[3],[4],..,[3,3,3,3,3,4,4,4,4,4]]
    mΠ     Product of each: [1,3,4,..,248832]
 Ṡ€ȯ       k is in this list.

Bahasa Wolfram (Mathematica) , 68 65 62 61 byte

If[#^#2<=1,1~Max~-Log@#2,Min[#0[#,#2-1,##4],#0[#/#3,##2]#3]]&

Cobalah online!

Bagaimana itu bekerja

Mengambil input sebagai [n,k,f1,f2,f3,...,fk](misalnya, [11,3,2,3,5]): nilai pertama adalah target n, yang kedua adalah jumlah faktor, dan semua frctors mengikuti.

Sejumlah teori nomor lain tantangan baru-baru ini dilipat menjadi mewah built-in (setidaknya, mereka menggunakan FactorInteger) jadi saya pikir saya akan mencoba sesuatu yang hanya menggunakan alat dasar. Solusi ini pada dasarnya mengatakan bahwa untuk menulis nsebagai produk dari faktor-faktor, kita menggunakan faktor pertama f1(dan berulang n/f1, lalu kalikan dengan f1) atau tidak (dan berulang pada daftar faktor yang lebih pendek), lalu gunakan min.

Rekursi turun ketika target kurang dari 1 atau ketika jumlah faktor adalah 0, yang kami periksa #^#2<=1sekaligus, dan kemudian menghasilkan 1 dalam kasus pertama dan Infinityyang terakhir dengan 1~Max~-Log@#2.

Fungsi ini memberikan sejumlah peringatan (tetapi masih berfungsi) kecuali Anda menjalankannya Quiet, karena pada akhirnya akan muncul kembali ke kasus-kasus di mana #3tidak ada, membuat cabang Ifsedih kedua yang tidak digunakan .

-3 byte: mengambil jumlah faktor sebagai input.

-3 byte terima kasih kepada @ngenisis: using ∞.

-1 byte, dan tidak ada ∞ambiguitas: #^#2cek.

Python 2 , 91 88 84 byte

f=lambda n,l:n<2or any(n%x<1and f(n/x,l)for x in l)
g=lambda n,l:n*f(n,l)or g(n+1,l)

Cobalah online!

Fungsi ini fmemeriksa secara rekursif jika nmerupakan produk dari kekuatan elemen l, ghanya pembungkus untuk mengontrol iterasi

Python, 55 byte

f=lambda n,l,x=1:min(f(n,l,x*e)for e in l)if x<n else x

Cobalah online!

Tanpa malu-malu menyalin skrip footer Rod untuk pengujian

Jelly , 13 byte

L⁹ṗ’⁸*P€ḟ⁹Ḷ¤Ṃ

Tautan diad mengambil daftar,, fdi sebelah kiri dan nomor n,, di sebelah kanan yang menghasilkan angka.

Cobalah online! Golfily inefisien - akan timeout untuk input dengan yang lebih tinggindan / atau lebih lamaf.

Bagaimana?

Kita tahu bahwa kekuatan faktor individu (sangat positif) tidak akan pernah perlu dilampaui n-1
... jadi mari kita periksa semua cara yang mungkin!

L⁹ṗ’⁸*P€ḟ⁹Ḷ¤Ṃ - Link: list, f; number, n
 ⁹            - chain's right argument, n
L             - length of f
  ṗ           - Cartesian power  ...e.g.: len(f)=2; n=3 -> [[1,1],[1,2],[1,3],[2,1],[2,2],[2,3],[3,1],[3,2],[3,3]]
   ’          - decrement (vectorises)
    ⁸         - chain's left argument, f
     *        - exponentiate (vectorises) - that is [f1^a, f2^b, ...] for each [a, b, ...] in the list formed from the Cartesian power
      P€      - product for €ach - that is f1^a * f2^b * ... for each [a, b, ...] in the list formed from the Cartesian power
           ¤  - nilad followed by link(s) as a nilad:
         ⁹    -   chain's right argument, n
          Ḷ   -   lowered range -> [0,1,2,3,...,n-1]
        ḟ     - filter discard - that is remove values less than n
            Ṃ - minimum

Retina , 76 byte

\d+
$*
1+;
$&$&
{+`;(1+)(\1)*(?=;.*\b\1\b)
;1$#2$*1
}`(1+);11+;
1$1;1$1;
\G1

Cobalah online! Tautan mengecualikan kasus uji paling lambat, tetapi masih agak lambat, jadi cobalah untuk tidak memalu server @ Dennis.

Pyth - 10 byte

Kehabisan memori sangat cepat.

f}T*My*QTE

Cobalah online di sini .

Jawaban yang masuk akal untuk 16 byte: fsm.A}RQ*Md./PTE

Mathematica, 85 byte

Min@Select[Flatten[1##&@@(s^#)&/@Tuples[0~Range~⌈Log[Min[s=#],d=#2]⌉,#3]],#>=d&]&

Memasukkan

[{list f}, n, jumlah elemen f]
[{57, 34, 12, 21}, 12532159, 4]

Japt , 10 byte

_k e!øV}aU

Uji secara online!

Tidak berfungsi pada kasus uji terakhir karena batas iterasi yang dirancang agar interpreter tidak berjalan selamanya (meskipun tidak banyak membantu di sini, karena membekukan browser saya selama satu jam ...)

Penjelasan

_k e!øV}aU    Implicit: U = input integer, V = array of factors
_      }aU    Starting at U, find the next integer Z where
 k              the factors of Z
   e            are such that every factor
    !øV         is contained in V (e!øV -> eX{VøX}, where VøX means "V contains X").
              Implicit: output result of last expression

Jelly , 9 byte

xŒPP€ḟḶ}Ṃ

Runtime dan penggunaan memori O (2 ^{n • panjang (f)} ) menjadikan ini solusi teoretis.

Cobalah online!

Haskell , 46 byte

Ini adalah port jawaban Python KSab yang sangat baik . Terima kasih kepada Laikoni untuk bantuan mereka dalam debugging dan golf jawaban ini di chatroom PPCG Haskell, Of Monads and Men . Selamat datang saran bermain golf! Cobalah online!

(#1)
(l#x)n|x<n=minimum[(l#(x*e))n|e<-l]|1>0=x

Mathematica, 73 byte

1±_=1>0;n_±f_:=Or@@(#∣n&&n/#±f&/@f);n_·f_:=NestWhile[#+1&,n,!#±f&]

Pada dasarnya sebuah port jawaban Rod 's Python . Mendefinisikan dua operator biner dan . mengembalikan jika merupakan produk dari elemen dan±·n±fTruenfFalse sebaliknya. n·fmemberikan bilangan bulat terkecili . Jika seseorang dapat menemukan cara untuk menghilangkan tes keterbagian, saya bisa menghemat 10 byte dengan menggunakan pengkodean ISO 8859-1.

Penjelasan

1±_=1>0;                         (* If the first argument is 1, ± gives True. *)
n_±f_:=Or@@(#∣n&&n/#±f&/@f);     (* Recursively defines ±. *)
                                 (* For each element of f, check to see if it divides n. *)
                                 (* For each element # that does, check if n/# is a product of elements of f. *)
n_·f_:=NestWhile[#+1&,n,!#±f&]   (* Starting with n, keep incrementing until we find an i that satisfies i±f. *)

R , 52 byte

function(n,f)min((y=(x=outer(f,0:n,"^"))%o%x)[y>=n])

Cobalah online!

Sudah 3 minggu, jadi saya pikir saya akhirnya akan memposting solusi saya sendiri. Ini adalah pendekatan brute force.

Namun, ada builtin:

R , 5 byte

nextn

Cobalah online!

Dari dokumen:

nextnmengembalikan bilangan bulat terkecil, lebih besar dari atau sama dengan n, yang dapat diperoleh sebagai produk dari kekuatan nilai yang terkandung di dalamnya factors. nextndimaksudkan untuk digunakan untuk menemukan panjang yang sesuai dengan argumen zero-pad fftsehingga transformasi dihitung dengan cepat. Nilai default untuk factorsmemastikan ini.

Namun, beberapa pengujian mengungkapkan bug dalam implementasi, seperti yang ditunjukkan oleh tautan TIO di atas.

nextn(91,c(2,6))harus mengembalikan 96, tetapi mengembalikan 128 sebagai gantinya. Ini jelas hanya terjadi ketika factorstidak semua relatif prima satu sama lain. Memang, kode C yang mendasarinya mengungkapkan bahwa nextndengan rakus mencoba untuk membagi masing-masing factorpada gilirannya sampai 1tercapai:

static Rboolean ok_n(int n, int *f, int nf)
{
    int i;
    for (i = 0; i < nf; i++) {
    while(n % f[i] == 0) {
        if ((n = n / f[i]) == 1)
        return TRUE;
    }
    }
    return n == 1;
}


static int nextn0(int n, int *f, int nf)
{
    while(!ok_n(n, f, nf))
    n++;
    return n;
}

Ini dapat diatasi dengan mengambil input dalam urutan menurun.

JavaScript (ES6), 53 50 byte

Disimpan 3 byte berkat @DanielIndie

Mengambil input dalam sintaks currying (n)(a).

n=>m=a=>(g=k=>k<n?a.map(x=>g(k*x)):k>m?0:m=k)(1)|m

Uji kasus

let f =

n=>m=a=>(g=k=>k<n?a.map(x=>g(k*x)):k>m?0:m=k)(1)|m

console.log(f(10)([2,3,5]))                // -> 10
console.log(f(17)([3,7]))                  // -> 21
console.log(f(61)([3,5,2,7]))              // -> 63
console.log(f(23)([2]))                    // -> 32
console.log(f(23)([3]))                    // -> 27
console.log(f(23)([2, 3]))                 // -> 24
console.log(f(31)([3]))                    // -> 81
console.log(f(93)([2,2,3]))                // -> 96
console.log(f(91)([2,4,6]))                // -> 96
console.log(f(1,)([2,3,5,7,11,13,17,19]))  // -> 1
console.log(f(151)([20,9,11]))             // -> 180
console.log(f(11616)([23,32]))             // -> 12167
console.log(f(11616)([23,32,2,3]))         // -> 11664 = 2^4 * 3^6
console.log(f(5050)([3,6,10,15,21,28,36,45,55,66,78,91,105,120,136,153,171,190,210])) // -> 5103 = 3^6 * 7
console.log(f(12532159)([57,34,12,21]))    // -> 14183424 = 12^5 * 57

Bagaimana?

n => a => (                 // given n and a
  g = k =>                  // g = recursive function taking k
    k < n ?                 // if k is less than n:
      a.map(x => g(k * x))  //   recursive calls to g with x * k for each x in a
    :                       // else:
      k > m ?               //   if k is greater than m and m is not set to NaN:
        0                   //     ignore this result
      :                     //   else:
        m = k               //     update m to k
  )(                        // initial call to g with:
    1,                      //   k = 1
    m = +a                  //   m = either NaN or the single integer contained in a
  ) | m                     // return m