Temukan Kekuatan Perdana Maksimal

23

Sebuah kekuatan utama adalah bilangan bulat positif n yang dapat ditulis dalam bentuk n = p k mana p adalah prima dan k adalah bilangan bulat positif. Sebagai contoh, beberapa kekuatan utama adalah [2, 3, 5, 4, 9, 25, 8, 27, 125].

Selanjutnya, pertimbangkan kekuatan utama 2. Ini adalah [2, 4, 8, 16, ...]dan dapat ditulis dalam bentuk 2 k . Mereka semua akan dimasukkan ketika mempertimbangkan kekuatan utama di bawah 20. Namun, 16 adalah kekuatan prima maksimal dengan basis prima 2 dalam rentang itu. Kekuatan prima p k adalah maksimal dalam suatu rentang jika itu adalah kekuatan tertinggi dari p dalam rentang itu. Kami hanya tertarik pada kekuatan prima maksimal di setiap rentang sehingga semua kekuatan prima yang lebih rendah harus dikecualikan.

Tujuan Anda adalah untuk menulis fungsi atau program yang mengambil bilangan bulat positif n dan output maksimal kekuatan utama dalam kisaran [2, 3, 4, ..., n].

Terima kasih kepada @ Peter Taylor untuk mengklarifikasi definisi kekuatan prima maksimal dan banyak lagi.

Aturan

  • Ini adalah jadi buat kode Anda sesingkat mungkin.
  • Kekuatan prima maksimal dapat berupa output dalam urutan apa pun tetapi tidak boleh ada duplikat.

Uji kasus

n      result
1      []
2      [2]
3      [2, 3]
4      [3, 4]
5      [3, 4, 5]
6      [3, 4, 5]
7      [3, 4, 5, 7]
20     [5, 7, 9, 11, 13, 16, 17, 19]
50     [11, 13, 17, 19, 23, 25, 27, 29, 31, 32, 37, 41, 43, 47, 49]
100    [11, 13, 17, 19, 23, 25, 29, 31, 37, 41, 43, 47, 49, 53, 59, 61, 64, 67, 71, 73, 79, 81, 83, 89, 97]
10000  <1229 results>
       [101, 103, 107, 109, 113, 127, 131, 137, 139, 149, ..., 9887, 9901, 9907, 9923, 9929, 9931, 9941, 9949, 9967, 9973]

Daftar lengkap kekuatan prima maksimal untuk 10.000 dapat ditemukan di sini .

mil
sumber

Jawaban:

16

Jelly , 7 4 byte

æḟÆR

Cobalah online!

Bagaimana itu bekerja

æḟÆR  Main link. Argument: n

  ÆR  Prime range; yield all primes in [1, ..., n].
æḟ    Power floor; round n down to the nearest power of each prime in the range.
Dennis
sumber
Oh begitu jelas sekali orang melihatnya!
Jonathan Allan
15
Power floorApa-apaan
JungHwan Min
1
Posting ini secara resmi meyakinkan saya untuk belajar Jelly.
Chandler Watson
10

Mathematica, 44 43 40 byte

Disimpan 4 byte berkat miles dan Martin Ender

n#^⌊#~Log~n⌋&/@Select[Range@n,PrimeQ]

(x=Prime@Range@PrimePi@#)^⌊x~Log~#⌋&

dan adalah 3karakter byte U+230Adan U+230Bmewakili \[LeftFloor]dan \[RightFloor]masing-masing.

Penjelasan:

masukkan deskripsi gambar di sini

Fungsi murni. #kependekan Slot[1]yang merupakan argumen pertama ke Function. PrimePi@#menghitung jumlah bilangan prima yang kurang atau sama dengan #, Range@PrimePi@#adalah daftar PrimePi[#]bilangan bulat positif pertama , dan demikian Prime@Range@PrimePi@#juga daftar bilangan prima lebih kecil atau sama dengan #(ini satu byte lebih pendek dari Select[Range@#,PrimeQ]). Simbol xadalah Setsama dengan daftar ini, kemudian diangkat ke Power ⌊x~Log~#⌋, yang merupakan daftar Floor[Log[n,#]]untuk setiap ndi x. Dalam Mathematica, menaikkan daftar ke daftar Powerlain dengan panjang yang sama menghasilkan daftar kekuatan elemen yang sesuai.

ngenisis
sumber
Saya pikir Range@#~Select~PrimeQakan lebih pendek dari Prime@Range@PrimePi@#... tapi ini dasi
Greg Martin
Itu angka yang bagus. Apakah itu dihasilkan menggunakan builtin atau dibuat secara manual?
mil
@miles Dibuat menggunakanTreeForm
ngenisis
Terima kasih. Saya tidak ingat pernah melihatnya, tapi ternyata sudah ada selamanya.
miles
7

MATL, 13 byte

ZqG:!^tG>~*X>

Cobalah secara Online!

Penjelasan

        % Implicitly grab the input as a number (N)
Zq      % Get an array of all primes below N
G:!     % Create an array from [1...N]
^       % Raise each prime to each power in this array which creates a 2D matrix
        % where the powers of each prime are down the columns
tG>~    % Create a logical matrix that is TRUE where the values are less than N
*       % Perform element-wise multiplication to force values > N to zero
X>      % Compute the maximum value of each column
        % Implicitly display the resulting array
Suever
sumber
7

Jelly , 8 byte

ÆR*ÆE€»/

Cobalah online!

Bagaimana itu bekerja

ÆR*ÆE€»/  Main link. Argument: n

ÆR        Prime range; yield all primes in [1, ..., n].
   ÆE€    Prime exponents each; yield the exponents of 2, 3, 5, ... of the prime
          factorization of each k in [1, ..., n].
          For example, 28 = 2² × 3⁰ × 5⁰ × 7¹ yields [2, 0, 0, 1].
  *       Exponentiation; raise the elements of the prime range to the powers
          of each of the exponents arrays.
      »/  Reduce the columns by maximum.
Dennis
sumber
6

Jelly , 12 9 byte

RÆEz0iṀ$€

Cobalah online! (Metode terlalu lambat untuk kasus 10000).

Bagaimana?

Membangun daftar p k di urutan p .

RÆEz0iṀ$€ - Main link: n                      e.g. 7
R         - range(n)                          [1 ,2  ,3    ,4  ,5      ,6    ,7]
 ÆE       - prime factor vector (vectorises)  [[],[1],[0,1],[2],[0,0,1],[1,1],[0,0,0,1]]
   z0     - transpose with filler 0           [[0,1,0,2,0,1,0],[0,0,1,0,0,1,0],[0,0,0,0,1,0,0],[0,0,0,0,0,0,1]]
       $€ - la$t two links as a monad, for €ach       ^             ^                   ^                   ^
     i    -     first index of                        4             3                   5                   7
      Ṁ   -     maximum                       [4,3,5,7]
Jonathan Allan
sumber
5

Pyth, 13 byte

m^ds.lQdfP_TS

Coba di sini!

        f   S -  filter(v, range(1, input))
         P_T  -   is_prime(T)
m             - map(v, ^)
    .lQd      -    log(input, d)
   s          -   int(^)
 ^d           -  d ** ^

Saya belum pernah bermain dengan Pyth sehingga tip golf apa pun dihargai.

Biru
sumber
5

Saya tidak bisa mendapatkan solusi Mathematica yang lebih pendek daripada solusi ngenisis , tetapi saya pikir saya akan menawarkan beberapa pendekatan alternatif (semoga menarik).

Mathematica, 65 byte

#/#2&@@@({#,#}&/@Range@#~Select~PrimeQ//.{a_,b_}/;a<=#:>{b a,b})&

Pertama-tama kita gunakan {#,#}&/@Range@#~Select~PrimeQuntuk membuat daftar semua bilangan prima dalam kisaran yang sesuai, tetapi dengan pasangan terurut dari setiap prime, seperti { {2,2}, {3,3}, ...}. Kemudian kami beroperasi pada daftar itu berulang kali dengan aturan penggantian {a_,b_}/;a<=#:>{b a,b}, yang mengalikan elemen pertama dari pasangan yang dipesan dengan yang kedua hingga elemen pertama melebihi input. Kemudian kita berlaku #/#2&@@@untuk output, untuk setiap pasangan yang dipesan, elemen pertama dibagi dengan yang kedua. (Mereka akhirnya disortir oleh prime yang mendasarinya: contoh outputnya adalah {16, 9, 5, 7, 11, 13, 17, 19}.)

Mathematica, 44 byte

Values@Rest@<|MangoldtLambda@#->#&~Array~#|>&

Fungsi von Mangoldt Λ(n)adalah fungsi jumlah teori yang menarik: itu sama dengan 0 kecuali nadalah seorang perdana listrik p k , dalam hal ini sama dengan log p(tidak log n). (Ini adalah log natural, tetapi itu tidak masalah.) Dengan demikian MangoldtLambda@#->#&~Array~#membuat array aturan { 0->1, Log[2]->2, Log[3]->3, Log[2]->4, Log[5]->5, 0->6, ... }yang panjangnya adalah bilangan bulat input.

Kami kemudian mengubah daftar aturan ini menjadi "asosiasi" menggunakan <|...|>. Ini memiliki efek mempertahankan hanya aturan terakhir dengan nilai tangan kiri yang diberikan. Dengan kata lain, itu akan membuang Log[2]->2dan Log[2]->4dan Log[2]->8dan hanya menyimpan Log[2]->16(dengan asumsi bahwa input antara 16 dan 31 untuk contoh ini). Oleh karena itu satu-satunya sisi kanan yang tersisa adalah kekuatan prima maksimal — kecuali untuk aturan yang tersisa 0->n, di mana ndaya non-prima terbesar hingga bilangan bulat input. Tetapi Restmembuang aturan yang tidak diinginkan, dan Valuesekstrak sisi kanan dari aturan dalam asosiasi. (Mereka akhirnya disortir seperti di atas.)

Versi yang sedikit lebih panjang (46 byte), yang menghitung jumlah penampilan masing-masing log pdan kemudian secara eksponensial dikonversi menjadi kekuatan prima maksimal:

E^(1##)&@@@Rest@Tally[MangoldtLambda~Array~#]&
Greg Martin
sumber
1
Penggunaan asosiasi dengan rapi. Mereka sudah keluar sejak 2014 tetapi saya tidak berpikir mereka telah melihat banyak kegunaan dalam golf. Sangat berguna untuk mengetahuinya mengganti kunci identik dengan nilai dari kiri ke kanan.
mil
4

CJam , 21 20 byte

Disimpan 1 byte berkat Martin Ender

ri_){mp},f{\1$mLi#}p

Cobalah online!

Penjelasan

ri                    e# Read an integer from input (let's call it n)
  _                   e# Duplicate it
   ){mp},             e# Push the array of all prime numbers up to and including n
         f{           e# Map the following block to each prime p:
           \          e#   Swap the top two elements of the stack
            1$        e#   Copy the second element down in the stack. Stack is now [p n p]
              mL      e#   Take the base-p logatithm of n
                i     e#   Cast to int (floor)
                 #    e#   Raise p to that power
                  }   e# (end of map block)
                   p  e# Print
Kucing Bisnis
sumber
4

Brachylog , 15 byte

⟧{ḋ=}ˢ⊇Xhᵐ≠∧X×ᵐ

Cobalah online!

Ini menghasilkan kekuatan dari yang terbesar hingga yang terkecil.

Ini sangat tidak efisien.

Penjelasan

⟧                   The Range [Input, Input - 1, ..., 1, 0]
 {  }ˢ              Select:
  ḋ=                  The elements of that range whose prime decompositions are lists of the
                      same element (e.g. [3,3,3]); output is those prime decompositions
      ⊇X            X is an ordered subset of that list of prime decompositions
       Xhᵐ≠         All first elements of the prime decompositions are different (that is,
                      X contains prime decompositions with different primes each times)
           ∧
            X×ᵐ     Output is the result of mapping multiplication to each element of X

Ini akan menemukan dekomposisi prime terbesar untuk setiap prime terlebih dahulu karena cara kerjanya: dari kiri ke kanan dan dari himpunan bagian terbesar ke terkecil.

Fatalisasi
sumber
4

Brachylog , 24 21 19 byte

3 + 2 byte disimpan berkat Fatalize!

Ini adalah pertama kalinya saya menggunakan Brachylog, dan saya tahu beberapa hal bisa dilakukan dengan cara yang lebih pendek, tapi saya senang itu berhasil: D

{≥.~^ℕ₁ᵐhṗ:.≜×>?∧}ᶠ

Cobalah online! (Nilai pengembalian dipesan oleh bilangan prima basis mereka)

Penjelasan:

{................}ᶠ           #Find all possible results of what's inside.
 ≥.                           #Input is >= than the output.
  .~^ℕ₁ᵐ                      #Output can be calculated as A^B, where A and B are
                              #Natural numbers >=1.
        hṗ                    #The first of those numbers (A) is prime
          :.≜×>?              #That same element (A), multiplied by the output
                              #is greater than the input - This means 
                              #that B is the maximal exponent for A.
                ∧             #No more restrictions on the output.
Leo
sumber
1
Besar! Anda dapat menyimpan dua byte dengan menggunakan nama variabel spesifik ?dan .untuk Input dan Output, alih-alih Idan X, dengan demikian:{≥N~^.hṗ:N×>?∧0<~t}ᶠ^ᵐ
Menghancurkan
1
Anda juga dapat menyimpan byte lain dengan menghapus 0<~tdan menyatakan bahwa setiap elemen dari Output .adalah ℕ₁ = [1, ..., +inf)seperti:{≥N~^.ℕ₁ᵐhṗ:N×>?∧}ᶠ^ᵐ
Fatalize
@Selamatalkan terima kasih! Saya akan memperbarui solusi dengan saran Anda :) Omong-omong, apakah Anda tahu mengapa solusi seperti {≥.~^ℕ₁ᵐhṗ:.×>?∧}ᶠ(menggunakan N langsung sebagai output) tidak berfungsi? Saya mencoba dulu sesuatu seperti ini, tetapi kemudian harus menggunakan X dan menerapkannya
Leo
2
Saya sebenarnya bertanya-tanya hal yang sama; ini mungkin karena langkah pelabelan implisit yang terjadi pada akhir predikat {...}ᶠyang menyebabkan perilaku aneh. Saya bermaksud mengubahnya dan saya akan melihat secara spesifik mengapa program ini tidak bekerja dengan cara yang sama seperti di atas.
Fatalkan
1
Ini benar-benar berfungsi jika Anda melakukannya seperti ini: {≥.~^ℕ₁ᵐhṗ:.≜×>?∧}ᶠDengan begitu Anda mendapatkan labelisasi yang benar. (Perubahan dibuat untuk spesifikasi sementara itu tetapi tidak benar-benar mengubah perilaku program khusus ini, sehingga tidak membuatnya tidak bersaing). Ini menghemat 2 byte
Fatalkan
3

05AB1E , 15 12 byte

ƒNpiN¹N.nïm,

Cobalah online!

Penjelasan

ƒ             # for N in [0 ... input]
 Npi          # if N is prime
    N         # push N
     ¹N.n     # push log_N(input)
         ï    # convert to int
          m   # raise N to this power
           ,  # print
Emigna
sumber
3

Utilitas Bash + GNU, 74 byte

seq $1|factor|sed "s@.*: \(\w*\)\$@\1;l($1);l(\1);print \"/^p\"@"|bc -l|dc

Cobalah online!

Nomor input dilewatkan sebagai argumen. Outputnya dicetak ke stdout. (Seperti biasa, stderr diabaikan.)

Output sampel:

./maximalprimepowers 100 2>/dev/null
64
81
25
49
11
13
17
19
23
29
31
37
41
43
47
53
59
61
67
71
73
79
83
89
97

./maximalprimepowers 10000 2>/dev/null | wc -l
1229

Begini cara kerjanya:

Sebut argumen N.

seqmenghasilkan semua angka dari 1 hingga N, dan factorfaktor semuanya.

Regex dalam panggilan ke sed mengidentifikasi garis-garis di mana nomor tersebut adalah P prima, dan menggantikan garis-garis itu dengan garis-garis yang berbentuk `

P;l(N);l(P);print "/^p"

(di mana P dan N diganti dengan nilai numerik aktualnya, dan semua yang lain disalin secara harfiah, bahkan tanda kutip dan titik koma, dan string print).

Baris-baris ini dimasukkan sebagai input ke bc -l; bc mencetak nilai dari tiga angka yang ditunjukkan, masing-masing diikuti oleh baris baru, dan kemudian mencetak karakter /^p. (Dalam bc, l (x) menunjukkan logaritma natural x.) JK K

String yang dicetak bc kemudian diumpankan sebagai input ke dc; dc mencetak nilai setiap P ^ (log (N) / log (P)) menggunakan bilangan bulat aritmatika (memotong); itulah kekuatan terbesar dari P yaitu <= N.

Satu hal yang dipoles di atas adalah apa yang terjadi pada garis yang dihasilkan oleh faktor-faktor yang tidak sesuai dengan bilangan prima. Garis-garis itu tidak cocok dengan regex dalam panggilan ke sed, jadi tidak ada penggantian dilakukan pada mereka. Akibatnya, garis-garis itu mulai dengan angka yang diikuti oleh titik dua, yang menghasilkan kesalahan ketika dimasukkan sebagai input bc. Tapi bc hanya mencetak ke stderr lalu, yang kita abaikan; itu tidak mencetak apa pun untuk stdout. Secara default, stderr diabaikan di PPCG .

Mitchell Spector
sumber
3

Haskell , 73 67 66 byte

p n=[last[x^i|i<-[1..n],x^i<=n]|x<-[2..n],all((>0).mod x)[2..x-1]]

Cobalah online! Pemakaian:

Prelude> p 50
[32,27,25,49,11,13,17,19,23,29,31,37,41,43,47]

Sunting: lepas 6 byte berkat Zgarb!

Penjelasan:

p n=[... x|x<-[2..n]                         ] -- list of all x in the range 2 to n
p n=[... x|x<-[2..n],        mod x<$>[2..x-1]] -- where the remainders of x mod the numbers 2 to x-1
p n=[... x|x<-[2..n],all(>0)$mod x<$>[2..x-1]] -- are all greater 0. This yields all primes in the range.

p n=[    [x^i|i<-[1..n]       ]|...] -- for each of those x generate the list of all x^i with i in the range 1 to n
p n=[last[x^i|i<-[1..n],x^i<=n]|...] -- where x^i is smaller or equal to n
p n=[last[x^i|i<-[1..n],x^i<=n]|...] -- and take the last (that is the largest) element
Laikoni
sumber
1
Saya pikir sisi kiri bisa last[x^i|i<-[1..n],x^i<=n].
Zgarb
@ Zgarb Terima kasih! Itu selalu daftar pemahaman, bukan ...
Laikoni
2

Jelly , 9 byte

Ræl/ÆF*/€

Satu byte lebih lama dari jawaban saya yang lain , tetapi selesai untuk input 10.000 adalah beberapa detik.

Cobalah online!

Bagaimana itu bekerja

Ræl/ÆF*/€  Main link. Argument: n

R          Range; yield [1, ..., n].
 æl/       Reduce by least common multiple.
    ÆF     Factor the LCM into [prime, exponent] pairs.
      */€  Reduce each pair by exponentiation.
Dennis
sumber
Ada juga versi 7 byte di Jelly yang selesai dengan cepat.
mil
Saya akan melihat 7 Anda dan membesarkan Anda 4.: P
Dennis
Wow, saya tidak tahu itu builtin juga. Itu membutuhkan kue.
mil
2

JavaScript (ES6), 118 120 119 114 112 105 byte

(n,r)=>(r=k=>[...Array(k-1)].map((_,i)=>i+2),r(n).filter(q=>r(q).every(d=>q%d|!(d%(q/d)*(q/d)%d)&q*d>n)))

Saran diterima. Ini agak lama, tetapi sepertinya layak diposkan karena melakukan semua pengujian keterbagian secara eksplisit daripada menggunakan bawaan yang terkait dengan bilangan prima.

Catatan:

  • Bilangan alami q adalah kekuatan utama <=> semua pembagi q adalah kekuatan dari perdana yang sama <=> untuk setiap d yang membagi q, satu dari d dan q / d adalah pembagi dari yang lain.
  • Jika q adalah kekuatan p, q adalah maksimal <=> q ​​* p> n <=> q ​​* d> n untuk setiap pembagi nontrivial d dari q.
Mikha
sumber
2

Sage, 43 byte

lambda i:[x^int(ln(i,x))for x in primes(i)]

Peta setiap prime dalam kisaran primes(i)ke kekuatan prima maksimal. lnhanya alias logsehingga menerima basis alternatif meskipun namanya hanya bisa menggunakan basis e.

busukxuan
sumber
Pikir ini python pada awalnya, melihat primesfungsinya dan menjadi sangat bersemangat. Jangan pernah mempercayai stackoverflow lagi.
sagiksp
@sagiksp Saya tidak mengerti, apa hubungannya dengan StackOverflow?
busukxuan
2

Haskell, 110 90 byte

s[]=[];s(x:t)=x:s[y|y<-t,y`rem`x>0];f n=[last.fst.span(<=n).scanl1(*)$repeat x|x<-s[2..n]]

--duperbarui per umpan balik Laikoni

brander
sumber
Ini melempar Exception: Prelude.last: empty listuntuk f 2dan f 3.
Laikoni
1
Juga f 4mengembalikan [2,3]bukannya [4,3], saya pikir Anda takeWhile(<n)kebutuhan untuk menjadi takeWhile(<=n). Namun menggunakan fst.spanbukannya takeWhilesatu byte lebih pendek.
Laikoni
2

Haskell , 70 byte

f n=[k|k<-[2..n],p:q<-[[d|d<-[2..k],mod k d<1]],k==p*p^length q,p*k>n]

Menentukan fungsi f. Cobalah online!

Penjelasan

Idenya adalah untuk menyaring rentang [2..n]untuk angka-angka kyang memuaskan k == p^length(divisors k)dan p*k > n, di mana padalah pembagi utama terkecil k.

f n=                -- Define f n as
 [k|                -- the list of numbers k, where
  k<-[2..n],        -- k is drawn from [2..n],
  p:q<-[            -- the list p:q is drawn from
   [d|              -- those lists of numbers d where
    d<-[2..k],      -- d is drawn from [2..k] and
    mod k d<1]      -- d divides k
   ],               -- (so p:q are the divisors of k except 1, and p is the smallest one),
  k==p*p^length q,  -- k equals p to the power of the divisor list's length
                    -- (so it's in particular a prime power), and
  p*k>n]            -- p*k, the next power of p, is not in the range [2..n].
Zgarb
sumber
1

PHP, 101 93 91 88 byte

hanya sedikit matematika sungguhan ...

for($n=$argv[$i=1];$n>$j=$i++;$j?:$r[$p=$i**~~log($n,$i)]=$p)for(;$i%$j--;);print_r($r);

kerusakan

for($n=$argv[$i=1];     // loop $i from 2 to $n
    $n>$j=$i++;             // 0.: init $j to $i-1
    $j?:                    // 2. if $i is prime
        $r[$p=$i**~~log($n,$i)]=$p) // 3. add maximum power to results
    for(;$i%$j--;);         // 1. prime check (if $i is prime, $j will be 0)
print_r($r);            // print results
Titus
sumber
1

JavaScript ES7, 93 byte

Ulangi secara berulang idari 0 hingga dan termasuk n. Jika iprima naikkan ke eksponen berlantai tertinggi yang membuatnya <= n( i ^ floor(log(n) / log(i)))

F=(n,i=n)=>i?[...((P=j=>i%--j?P(j):1==j)(i)?[i**((l=Math.log)(n)/l(i)|0)]:[]),...F(n,--i)]:[]
George Reith
sumber