Salah satu cara untuk merepresentasikan bilangan asli adalah dengan mengalikan eksponen bilangan prima. Sebagai contoh, 6 dapat diwakili oleh 2 ^ 1 * 3 ^ 1, dan 50 dapat diwakili oleh 2 ^ 1 * 5 ^ 2 (di mana ^ menunjukkan eksponen). Jumlah bilangan prima dalam representasi ini dapat membantu menentukan apakah lebih pendek menggunakan metode representasi ini, dibandingkan dengan metode lain. Tetapi karena saya tidak ingin menghitung ini dengan tangan, saya memerlukan program untuk melakukannya untuk saya. Namun, karena saya harus mengingat program sampai saya pulang, itu harus sesingkat mungkin.

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 input, sebagaimana diuraikan dalam pendahuluan.

Kasus uji:

24      -> 2 (2^3*3^1)
126     -> 3 (2^1*3^2*7^1)
1538493 -> 4 (3^1*11^1*23^1*2027^1)
123456  -> 3 (2^6*3^1*643^1)

Ini adalah OEIS A001221 .

Mencetak:

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

MATL , 4 3 byte

-1 byte terima kasih kepada Luis Mendo

YFz

Cobalah online!

YF         Exponents of prime factors
  z        Number of nonzeros

Jawaban asli:

Yfun

Cobalah online!

Sebuah Yfunjawaban.

          (Implicit input)
Yf         Prime factorization
  u        Unique
   n       Numel
           (Implicit output)

05AB1E , 2 byte

^{jawaban lain yang cukup membosankan ...}

fg

Program lengkap yang menerima input numerik dan mencetak hasilnya

Cobalah online!

Bagaimana?

fg - implicitly take input
f  - get the prime factors with no duplicates
 g - get the length
   - implicit print

Mathematica, 7 byte

PrimeNu

Yup, ada built-in.

Mathematica, 21 byte

Length@*FactorInteger

Jauh sekali.

Gaia , 2 byte

^{Namun jawaban lain yang cukup membosankan ... --- J. Allan}

ḋl

Cobalah online!

• ḋ- Faktorisasi utama sebagai [prima, eksponen] .

• l - Panjangnya.

Python 2, 56 byte

f=lambda n,p=2,k=1:n/p and[f(n,p+1),k+f(n/p,p,0)][n%p<1]

Retina , 31 30 byte

&`(?!(11+)\1+$)(11+)$(?<=^\2+)

Masukan dalam bentuk unary.

Terima kasih kepada @MartinEnder untuk bermain golf 1 byte!

Cobalah online! (termasuk konverter desimal ke unary)

Bagaimana itu bekerja

Karena program terdiri dari satu regex dengan &pengubah, Retina hanya menghitung jumlah pertandingan yang tumpang tindih . Input diasumsikan terdiri dari n pengulangan 1 dan tidak ada yang lain.

Penampakan negatif

(?!(11+)\1+$)

cocok di lokasi antara 1 yang tidak diikuti oleh dua atau lebih 1 ( 11+), diikuti oleh satu atau lebih pengulangan dengan jumlah yang sama 1 ( \1+), diikuti oleh akhir input ( $).

Sejumlah komposit ab dengan a, b> 1 dapat ditulis sebagai b pengulangan dari suatu pengulangan dari 1 , sehingga lookahead pertandingan hanya lokasi diikuti oleh p pengulangan dari 1 , di mana p = 1 atau p adalah prima.

Regex

(11+)$

pastikan p> 1 dengan membutuhkan setidaknya dua 1 's ( 11+) dan menyimpan ekor 1 ' s dalam kelompok tangkapan kedua ( \2).

Akhirnya, tampilan positif di belakang

(?<=^\2+)

memverifikasi bahwa seluruh input terdiri dari kejadian kp ( k ≥ 1 ) dari 1 , memverifikasi bahwa p membagi input.

Dengan demikian, setiap pertandingan sesuai dengan pembagi prime yang unik p .

Utilitas Bash + GNU, 33

• 1 byte disimpan berkat @Dennis

factor|grep -Po ' \d+'|uniq|wc -l

Cobalah online .

Penjelasan

factor|                            # Split input into prime factors
       grep -Po ' \d+'|            # group factors onto lines
                       uniq|       # remove duplicates
                            wc -l  # count the lines

Jelly , 3 byte

^{jawaban yang sangat membosankan ...}

ÆFL

Tautan monadik yang mengambil nomor dan mengembalikan nomor

Cobalah online!

Bagaimana?

ÆFL - Link: number, n
ÆF  - prime factorisation as a list of prime, exponent pairs
  L - length

Ohm v2 , 2 byte

ml

Cobalah online!

Dua built-in tepat bersebelahan dalam dokumentasi lol.

Jelly , 2 byte

^{Namun jawaban lain yang cukup membosankan ... --- J. Allan}

Æv

Cobalah online!

Built-in.

Alice , 10 byte

/o
\i@/Dcd

Cobalah online!

Penjelasan

/o
\i@/...

Ini hanya kerangka kerja standar untuk program linear aritmatika-berat yang membutuhkan I / O desimal. Program yang sebenarnya itu sendiri hanyalah:

Dcd

Yang tidak:

D    Deduplicate prime factors. Does what it sounds like: for every p^k which
     is a divisor n, this divides n by p^(k-1).
c    Push the individual prime factors of n. Since we've deduplicated them
     first, the number of factors is equal to the value we're looking for.
d    Push the stack depth, i.e. the number of unique prime factors.

JavaScript 45 byte

* Untuk @SEJPM meminta penjelasan: apa yang saya lakukan di sini adalah ini mulai dari 2 - n (yang berubah, dan akhirnya akan menjadi faktor utama terbesar) - sekarang jika angka saat ini dibagi ni ingin menghitungnya hanya sekali (bahkan meskipun itu bisa menjadi faktor 2 * 2 * 2 * 3 - 2 dihitung sekali) - jadi "j" muncul di gambar, ketika j tidak ditentukan dalam panggilan fungsi - j akan menerima nilai dari " undefined ", dan ketika n% i == 0 maka saya memanggil fungsi dengan j = 1 pada panggilan berikutnya) - dan kemudian saya hanya menambahkan 1 ketika j sama dengan undefined yaitu! j + Function (n / i, i, ( j = 1 atau hanya 1)). saya tidak mengubah saya dalam hal ini karena mungkin masih dapat dibagi oleh saya lagi (2 * 2 * 3) tetapi kemudian j akan sama dengan 1 dan itu tidak akan dihitung sebagai faktor. harap saya jelaskan dengan cukup baik.

P=(n,i=2,j)=>i>n?0:n%i?P(n,i+1):!j+P(n/i,i,1)

console.log(P(1538493)==4);
console.log(P(24)==2);
console.log(P(126)==3);
console.log(P(123456)==3);

jika prime terakhir sangat besar dari itu akan memiliki panggilan max stack-jika itu masalah saya bisa membuat yang berulang

CJam , 7 5 byte

Terima kasih kepada Martin Ender untuk 2 byte off!

{mF,}

Blok anonim (fungsi) yang mengharapkan nomor input pada tumpukan dan menggantinya dengan nomor output.

Cobalah online! Atau verifikasi semua kasus uji .

Penjelasan

{   }   e# Define block
 mF     e# List of (prime, exponent) pairs
   ,    e# Length

Brachylog , 3 byte

ḋdl

Cobalah online!

Penjelasan

ḋ      Prime decomposition
 d     Remove duplicates
  l    Length

Pyth, 3 byte

l{P

Suite uji

Panjang ( l) dari set ( {) faktor prima ( P) dari input.

Sekam , 3 byte

Lup

Cobalah online!

Penjelasan

  p  -- prime factors
 u   -- unique elements
L    -- length

Sebenarnya , 2 byte

^{Namun jawaban lain yang cukup membosankan ... --- J. Allan}

yl

Cobalah online!

Karakter pertama dapat diganti dengan w.

Pyke , 3 byte

P}l

Coba di sini!

Python 3 , 68 67 byte

1 byte dihapus berkat @ Mr.Xcoder

lambda n:sum(n%k<all(k%j for j in range(2,k))for k in range(2,n+1))

Ini kali untuk kasus uji terbesar. Cobalah online!

Angka R +, 30 14 byte

16 byte dihapus berkat @Giuseppe

numbers::omega

Juga, ini adalah Coba online !! tautan per @Giuseppe.

Cembung , 3 byte

mF,

Cobalah online!

Pari / GP , 5 byte

Saya tidak tahu mengapa ini disebut nu di Mathematica tetapi omega di Pari / GP.

omega

Cobalah online!

Haskell , 58 byte

-4 byte terima kasih kepada @Laikoni

f n=sum[1|x<-[2..n],gcd x n>1,all((>)2.gcd x)[2..x-1]]

Cobalah online!

Penjelasan

Pada dasarnya menghasilkan semua bilangan prima paling besar ndan memfilternya untuk menjadi faktor n dan kemudian mengambil hasil yang panjang.

f n=                                                   -- main function
    sum[                                             ] -- output the length of the list
        1|x<-[2..n],                                   -- consider all potential primes <=n
                                                       -- and insert 1 into the list if predicates are satisfied
                    gcd x n>1,                         -- which are a factor of n
                              all(          )[2..x-1]  -- and for which all smaller numbers satisfy
                                  (>)2.                -- 2 being larger than
                                       gcd x           -- the gcd of x with the current smaller number

Japt, 5 4 byte

â èj

Cobalah

Dapatkan pembagi ( â) dan hitung ( è) bilangan prima ( j).

ARBLE , 28 byte

len(unique(primefactors(n)))

Cobalah online!

Ini adalah solusi yang sangat literal

Dyalog APL , 17 byte

⎕CY'dfns'
≢∪3pco⎕

Cobalah online!

Python 2 ,  63  55 byte

^{Jawaban yang jauh lebih menarik ...}

-8 byte berkat Jonathan Frech (menggunakan argumen dengan default untuk pasca-penyesuaian hasil bilangan prima dari 0ke 1- jauh lebih baik daripada lambda pembungkus !!)

f=lambda n,o=1:sum(n%i+f(i,0)<1for i in range(2,n))or o

Fungsi rekursif mengambil bilangan bulat positif n,, dan mengembalikan bilangan bulat positif, hitung.

Cobalah online! Sangat tidak efisien, jangan repot-repot dengan test case lainnya.

J, 12 byte

{:@$@(__&q:)

q: adalah fungsi eksponen utama J, memberikan argumen __ menghasilkan matriks yang baris pertama adalah semua faktor prima nol dan baris ke-2 adalah eksponen mereka.

Kami mengambil bentuk $matriks itu - baris demi kolom - jumlah kolom adalah jawaban yang kami cari.

{: memberi kita item terakhir dari daftar dua item ini (baris num, kolom num), dan karenanya jawabannya.

Cobalah online!

Java (OpenJDK 9) , 67 byte

n->{int c=0,p=1;for(;p<n;)if(n%++p<1)for(c++;n%p<1;n/=p);return c;}

Cobalah online!

Javascript ES6, 56 karakter

n=>eval(`for(q=2,r=0;q<=n;++q)n%q||(n/=q,r+=!!(n%q--))`)

Uji:

f=n=>eval(`for(q=2,r=0;q<=n;++q)n%q||(n/=q,r+=!!(n%q--))`)
console.log([24,126,1538493,123456].map(f)=="2,3,4,3")