Bangga dalam factorisation utama

9

Saya melihat tantangan utama lain yang muncul di PPCG, dan saya sangat menyukai saya bilangan prima. Kemudian saya salah membaca teks pengantar, dan bertanya-tanya apa otak kreatif di sini telah muncul.

Ternyata pertanyaan yang diajukan sepele, tetapi saya bertanya-tanya apakah hal yang sama berlaku untuk pertanyaan yang saya baca (salah):

6 dapat diwakili oleh 2 ^ 1 * 3 ^ 1, dan 50 dapat diwakili oleh 2 ^ 1 * 5 ^ 2 (di mana ^ menunjukkan eksponensial).

Tugas Anda:

Tulis program atau fungsi untuk menentukan berapa banyak bilangan prima yang berbeda dalam representasi angka ini.

Memasukkan:

Integer n sedemikian sehingga 1 <n <10 ^ 12, diambil dengan metode normal apa pun.

Keluaran:

Jumlah bilangan prima berbeda yang diperlukan untuk mewakili faktor prima unik n.

Kasus uji:

Input      Factorisation      Unique primes in factorisation representation
24         2^3*3^1            2 (2, 3)
126        2^1*3^2*7^1        3 (2, 3, 7)
8          2^3                2 (2, 3)
64         2^6                1 (2) (6 doesn't get factorised further)
72         2^3*3^2            2 (2, 3)
8640       2^6*3^3*5^1        3 (2, 3, 5)
317011968  2^11*3^5*7^2*13^1  6 (2, 3, 5, 7, 11, 13)
27         3^3                1 (3)

Ini bukan urutan OEIS.

Mencetak:

Ini adalah kode-golf , skor terendah dalam byte menang!

code-golf math primes integer pbeentje
sumber
Untuk apa hasil yang diharapkan 64? Apakah 2 (2,3)(karena 6 dapat direpresentasikan sebagai 2 * 3) atau 1 (2)(abaikan 6)?
Emigna
untuk 64hasil yang diharapkan adalah 1 (2). Saya suka ide melakukannya secara rekursif, tapi bukan itu cara saya membaca pertanyaan aslinya. Saya pikir 8640itu kasus uji yang cocok, tetapi seharusnya lebih eksplisit - terima kasih.
pbeentje
Anda mengklaim ini bukan urutan OEIS. Bukankah A001221, nilai-nilai fungsi omega (kecil)?
Gray Taylor
A001221 serupa, tetapi mulai menyimpang pada istilah 8 dan 9 (di sini 2, A001221 1) karena dimasukkannya eksponen sebagai prima dalam latihan ini.
pbeentje
Ah, begitu. Tuliskan factorisation utama, lalu lihat berapa banyak bilangan prima yang saya tulis (terlepas dari peran yang mereka mainkan). Saya ingin tahu apa yang terjadi jika Anda melangkah lebih jauh dan memfaktorkan eksponen ...
Gray Taylor

Jawaban:

5

Mathematica, 39 byte

Count[Union@@FactorInteger@#,_?PrimeQ]&

Cobalah online!

terima kasih kepada Martin Ender (-11 bytes)

J42161217
sumber
Casesternyata lebih pendek dari Select(-4 byte): Tr[1^Union@Cases[FactorInteger@#,_?PrimeQ,2]]&(melewati semua test case pada kernel baru)
JungHwan Min
Bagaimana dengan Count[Union@@FactorInteger@#,_?PrimeQ]&? (Belum memeriksa semua kasus uji.)
Martin Ender
@ MartinEnder sepertinya harusnya berfungsi. Lewati semua test case juga.
JungHwan Min
5

05AB1E , 9 7 byte

Disimpan 2 byte berkat Kevin Cruijssen

ÓsfìÙpO

Cobalah online!

Penjelasan

Ó        # push the prime factor exponents of the input
 sfì     # prepend the prime factors of the input
    Ù    # remove duplicates
     p   # check each if it is prime
      O  # sum
Emigna
sumber
1
-1 byte dengan menggunakan €pOsetelah menggabungkan faktor prima dan eksponen:ÓsfìÙ€pO
Kevin Cruijssen
@KevinCruijssen: Terima kasih! Sebenarnya menghemat 2 karena €tidak diperlukan.
Emigna
Ah, tentu saja .. Wow, tidak yakin bagaimana saya melewatkan itu, haha ​​xD
Kevin Cruijssen
4

Jelly ,  9  7 byte

ÆFFQÆPS

Cobalah online! atau Lihat Test suite.

Bagaimana?

ÆFFQÆPS ~ Program lengkap.

ÆF ~ Faktorisasi utama sebagai pasangan [prima, eksponen].
  F ~ Ratakan.
   Q ~ Deduplicate.
    ÆP ~ Untuk masing-masing, periksa apakah itu prima. 1 jika Benar, 0 jika Salah.
      S ~ Jumlah.
Tuan Xcoder
sumber
4

Gaia , 6 byte

ḋ_uṗ¦Σ

Cobalah online!

  • ḋ menghitung faktorisasi utama, sebagai pasangan [prima, eksponen] .

  • _ ratakan daftar.

  • u menghapus elemen duplikat.

  • ṗ¦memetakan melalui elemen dan mengembalikan 1 jika bilangan prima ditemukan, 0 sebaliknya.

  • Σ meringkas daftar.

Tuan Xcoder
sumber
3

CJam (13 byte)

{mFe__&:mp1b}

Test suite online

Ini cukup mudah: dapatkan bilangan prima dengan banyak, kurangi ke nilai yang berbeda, filter bilangan prima, hitung.

Sayangnya Martin menunjukkan beberapa kasus yang tidak ditangani oleh trik yang agak menarik dalam jawaban asli saya, meskipun ia juga memberikan penghematan 1-byte dengan mengamati bahwa sejak mpmemberi 0atau 1dapat dipetakan daripada disaring.

Peter Taylor
sumber
2

Ohm v2 , 6 5 byte

-1 byte terima kasih kepada @ Mr.Xcoder

ä{UpΣ

Cobalah online!

Cinaski
sumber
5 byte:ä{UpΣ
Tn. Xcoder
@ Mr.Xcoder Terima kasih! Saya mencari built-in itu tetapi tidak dapat menemukannya ..
Cinaski
1

Sebenarnya , 7 byte

w♂i╔♂pΣ

Cobalah online!

Penjelasan:

w♂i╔♂pΣ
w        factor into [prime, exponent] pairs
 ♂i      flatten to 1D list
   ╔     unique elements
    ♂p   for each element: 1 if prime else 0
      Σ  sum
Mego
sumber
1

Python 2 , 142 135 119 byte

f=lambda n,d=2:n-1and(n%d and f(n,d+1)or[d]+f(n/d))or[]
p=f(input())
print sum(f(n)==[n]for n in set(p+map(p.count,p)))

Cobalah online!

ovs
sumber
1

Sekam ,  11  10 byte

#ṗuS+omLgp

Cobalah online!

EDIT: Disimpan 1 byte berkat Zgarb .

Tuan Xcoder
sumber
1
#ṗuS+omLgpmenghemat satu byte.
Zgarb
1

Brachylog , 7 byte

ḋọcdṗˢl

Cobalah online!

           The output
      l    is the length of
  c        the concatenated
 ọ         list of pairs [value, number of occurrences]
ḋ          from the prime factorization of
           the input
   d       with duplicates removed
    ṗˢ     and non-primes removed.

Versi 9 byte yang menyenangkan: ḋọ{∋∋ṗ}ᶜ¹

String yang tidak terkait
sumber
0

Angka R +, 92 byte

function(n)sum(1|unique((x=c((r=rle(primeFactors(n)))$l,r$v))[isPrime(x)]))
library(numbers)

Cobalah online!

Giuseppe
sumber
0

J, 20 byte

3 :'+/1 p:~.,__ q:y'

Dihitung dengan tangan lol, jadi beri tahu saya jika ini tidak aktif.

Ada saran bermain golf?

Pengajuan membosankan: ratakan tabel faktorisasi utama dan hitung bilangan prima.

cole
sumber
0

Pari / GP , 47 byte

n->#Set(select(isprime,concat(Vec(factor(n)))))

Cobalah online!

alephalpha
sumber
0

Javascript (ES6), 145 byte

n=>{for(a=[b=l=0],q=n,d=2;q>=2;)q%d?(b&&(a.push(0),l++),d++,b=0):(q/=d,a[l]++,b=1);for(i in a){for(d=1,e=a[i];e%d;d++);e-d||n%e&&l++};return l+1}
Naruyoko
sumber