Jumlah faktor prima

27

2013 memiliki faktorisasi utama 3*11*61. 2014 memiliki faktorisasi utama 2*19*53. Properti menarik mengenai faktorisasi ini adalah bahwa terdapat bilangan prima yang berbeda dalam faktorisasi 2013 dan 2014 bahwa jumlah ke nomor yang sama: 11+61=19+53=72.

Tulis sebuah program atau fungsi yang mengambil input dua bilangan bulat positif lebih besar dari 1 dan mengembalikan nilai kebenaran jika ada jumlah faktor prima terpilih dari satu angka yang sama dengan jumlah faktor prima terpilih di angka kedua, dan nilai falsey sebaliknya.


Klarifikasi

  • Lebih dari dua faktor utama dapat digunakan. Tidak semua faktor utama dari jumlah tersebut perlu digunakan dalam penjumlahan. Jumlah bilangan prima yang digunakan dari dua bilangan tidak harus sama.
  • Bahkan jika suatu prima dinaikkan ke suatu daya yang lebih besar dari 1 dalam faktorisasi suatu bilangan, ia hanya dapat digunakan sekali dalam jumlah bilangan prima untuk bilangan tersebut.
  • 1 bukan prima.
  • Kedua nomor input akan kurang dari 2^32-1.

Uji kasus

5,6
    5=5
    6=2*3
    5=2+3
==>True

2013,2014
    2013=3*11*61
    2014=2*19*53
    11+61=19+53
==>True

8,15
    8=2^3
    15=3*5
    No possible sum
==>False

21,25
    21=3*7
    25=5^2
    No possible sum (can't do 3+7=5+5 because of exponent)
==>False

Ini kode golf. Aturan standar berlaku. Kode terpendek dalam byte menang.

Arcturus
sumber
6
Saya suka tantangan seperti ini, tetapi untuk bahasa golf, ini akan menjadi rantai bawaan: faktor, uniquify, himpunan bagian, jumlah, jumlah, tumpang tindih.
xnor
Bisakah kita mengambil input sebagai array dua item?
ETHproductions
@ EHProduk Secara default, ya.
lirtosiast
Bagaimana dengan 14 (2 * 7) dan 21 (3 * 7), apakah itu true, ketika mereka berbagi faktor 7?
Simon Forsberg
@SimonForsbergMcFeely Ya
Arcturus

Jawaban:

10

Julia, 95 93 byte

g(x)=reduce(vcat,map(p->map(sum,p),partitions([keys(factor(x))...])))
f(a,b)=g(a)∩g(b)!=[]

Fungsi utama adalah fdan itu memanggil fungsi pembantu g.

Tidak Disatukan:

function g(x::Integer)
    # Find the sum of each combination of prime factors of the input
    return reduce(vcat, map(p -> map(sum, p), partitions([keys(factor(x))...])))
end

function f(a::Integer, b::Integer)
    # Determine whether there's a nonzero intersection of the factor
    # sums of a and b
    return !isempty(g(a)  g(b))
end

Disimpan 2 byte berkat Darth Alephalpha

Alex A.
sumber
3
Saya perhatikan ini diturunkan. Apakah ada sesuatu yang saya abaikan? Jika itu salah, saya akan senang memperbaikinya, tetapi seperti itu berfungsi baik untuk saya dan melewati semua kasus uji.
Alex A.
Saya pikir map(p->maplebih pendek dari (m=map)(p->m.
alephalpha
@DarthAlephalpha Panggilan yang bagus, terima kasih.
Alex A.
7

Pyth, 11 byte

t@FmsMy{PdQ

Masukan dalam formulir 30,7.

t@FmsMy{PdQ     implicit: Q=input tuple
      y         powerset of
       {        unique elements of
        Pd      prime factorizations of d
    sM          Map sum over each element of the powerset
    sMy{Pd      lambda d: all sums of unique prime factors of d
   m      Q     Map over Q. Produces a two-element list.
 @F             Fold list intersection
t               Remove first element, which is a 0.
                If no other common sums, the remaining empty list is falsy.
lirtosiast
sumber
1
Ini sekarang identik dengan jawaban Pyth yang lain, dengan pengecualian satu huruf yang dipindahkan;)
ETHproduksi
@ ETHproductions saya jawab sebelum Maltysen memperbaiki milik mereka; jadi saya akan menyimpannya.
lirtosiast
7

Pyth - 17 12 11 byte

Terima kasih kepada @FryAmTheEggman untuk memperbaiki jawaban saya dan menghemat satu byte.

@FmsMty{PdQ

Test Suite .

Maltysen
sumber
Saya pikir menggunakan tykarya dan menyimpan selamat tinggal?
FryAmTheEggman
@FryAmTheEggman terima kasih!
Maltysen
17
@Maltysen Anda melewatkan kesempatan emas untuk mengatakan "ty"
undergroundmonorail
4

Haskell, 115 106 byte

import Data.Numbers.Primes
import Data.List
p=map sum.tail.subsequences.nub.primeFactors
a#b=p a/=p a\\p b

Contoh penggunaan: 2013 # 2014-> True.

pmembuat daftar semua faktor utama argumennya, menghapus duplikat, membuat daftar semua urutan, menghapus yang pertama (yang selalu merupakan daftar kosong) dan akhirnya menjumlahkan kalimat berikutnya. #memeriksa apakah p atidak sama dengan perbedaan p a \\ p b. Jika tidak sama, mereka memiliki setidaknya satu elemen yang sama.

nimi
sumber
3

Japt, 25 byte

[UV]=N®k â à mx};Ud@J<VbX

Output trueatau false. Cobalah online!

Tanpa penjelasan dan penjelasan

[UV]=N®   k â à mx};Ud@ J<VbX
[UV]=NmZ{Zk â à mx};UdX{J<VbX

          // Implicit: N = list of inputs
[UV]=N    // Set variables U and V to the first to items in N,
mZ{    }  // with each item Z mapped to:
Zk        //  Generate list of Z's factors.
â         //  Keep only the unique items.
à         //  Generate all combinations.
mx        //  Sum each combination.
UdX{      // Check if any item X in U fulfills this condition:
J<VbX     //  -1 is less than V.indexOf(X).
          // Implicit: output last expression

Untuk byte tambahan, Anda dapat membagi kode faktorize-unik-gabungkan-jumlah antara kedua input, dengan keuntungan tambahan karena memiliki kompleksitas waktu O(O(25-byte version)^2):

Uk â à mx d@J<Vk â à mx bX
Produksi ETH
sumber
3

CJam, 23 byte

q~{mf_&0a\{1$f++}/}/&0-

Uji di sini.

Nilai sebenarnya adalah semua jumlah umum yang digabungkan, nilai falsy adalah string kosong.

Penjelasan

q~     e# Read and evaluate input.
{      e# For each of the two numbers...
  mf   e# Get the prime factors.
  _&   e# Remove duplicates.
  0a\  e# Put an array containing a 0 below to initialise the list of possible sums.
  {    e# For each prime factor...
    1$ e#   Make a copy of the available sums so far.
    f+ e#   Add the current factor to each of them.
    +  e#   Combine with the list of sums without that factor.
  }/
}/
&      e# Set intersection between the two lists of sums.
0-     e# Remove the 0 which is always in the intersection.
Martin Ender
sumber
3

Brachylog , 10 9 byte

{ḋd⊇+ℕ₁}ᵛ

Cobalah online!

Predikat berhasil kembali [the sum, the sum]jika ada, dan gagal jika jumlahnya tidak ada.

{            Start of inline predicate.
 ḋ           The prime factors of the input,
  d          with duplicates removed.
   ⊇         Some subset of the unique prime factors
    +ℕ₁      has a sum greater than 0 which is output.
       }ᵛ    The predicate can have the same output for both elements of the input.

-1 byte, terima kasih kepada Fatalize (pembuat Brachylog) yang mengingatkan saya bahwa predikat meta- verifikasi ada.

String yang tidak terkait
sumber
1
Anda dapat menggunakan ᵛ - verifyalih-alih ˢ=menyimpan satu byte.
Fatalkan
2

MATL , 23 byte

2:"iYfutn2w^1-:B!Y*]!=z

Gunakan rilis saat ini, 2.0.2 , yang lebih awal dari tantangan ini.

Angka-angka disediakan sebagai dua input terpisah. Output adalah 0atau 1.

Contoh

>> matl 2:"iYfutn2w^1-:B!Y*]!=z
> 2013
> 2014
1

Penjelasan

2:           % vector of two numbers, to generate two iterations
"            % for loop
  i          % input number                                                 
  Yfu        % get prime factors without repetitions
  tn         % duplicate and get number of elements in array N 
  2w^1-:     % numbers from 1 to 2^N                                        
  B!Y*       % convert to binary, transpose and matrix multiply to produce all sums
]            % end                                                      
!=z          % true if any value is equal to any other
Luis Mendo
sumber
2

Mathematica, 58 byte

Tr/@Rest@Subsets[#&@@@FactorInteger@#]&/@IntersectingQ@##&

Penjelasan:

Ini adalah fungsi anonim.

Pertama, IntersectingQperiksa apakah dua daftar berpotongan. Tetapi inputnya adalah angka, bukan daftar, jadi tetap tidak dievaluasi. Misalnya, jika inputnya adalah 2013dan 2014, kemudian IntersectingQ@##&kembali IntersectingQ[2013, 2014].

Tr/@Rest@Subsets[#&@@@FactorInteger@#]&adalah fungsi anonim lain yang mengambil bilangan bulat, mendapatkan daftar faktor prima tanpa pengulangan, mengambil set daya, menghapus set kosong, dan kemudian mengambil jumlah setiap set. Jadi Tr/@Rest@Subsets[#&@@@FactorInteger@#]&[2013]kembali {3, 11, 61, 14, 64, 72, 75}.

Kemudian petakan di Tr/@Rest@Subsets[#&@@@FactorInteger@#]&atas ekspresi IntersectingQ[2013, 2014]. Tr/@Rest@Subsets[#&@@@FactorInteger@#]&[2013]dan Tr/@Rest@Subsets[#&@@@FactorInteger@#]&[2014]]daftar, sehingga kami bisa mendapatkan hasil kumpulkan saat ini.

alephalpha
sumber
Panggilan IntersectingQpertama itu luar biasa! :)
Martin Ender
Bisakah Anda menambahkan penjelasan?
Lynn
2

PARI / GP , 98 byte

Factor, ambil primes ( [,1]), loop over himpunan bagian kosong, jumlah, dan uniq, kemudian memotong hasil ini untuk dua angka. Nilai yang dikembalikan adalah jumlah persimpangan, yang benar kecuali mereka adalah 0.

f(n,v=factor(n)[,1])=Set(vector(2^#v-1,i,vecsum(vecextract(v,i))))
g(m,n)=#setintersect(f(m),f(n))
Charles
sumber
2

APL (Dyalog Extended) , 23 17 byte SBCS

-5 Terima kasih kepada ngn

Fungsi infiks diam-diam anonim.

1<≢⍤∩⍥(∊0+⍀.,∪⍤⍭)

Cobalah online!

⍥{... } terapkan fungsi anonim berikut untuk kedua argumen:

 faktor utama

 kemudian

 yang unik dari mereka

0+⍀., pengurangan tabel penambahan nol digabungkan untuk setiap faktor

ϵ daftar (ratakan)

 persimpangan

 kemudian

 penghitungan dari mereka

1< apakah ada lebih dari satu? (satu karena jumlah tanpa faktor)

Adám
sumber
hanya menggunakan fitur dari dyalog yang tepat: p+.×⊤1↓⍳2*≢p←->1↓∊(⊢,+)/0,⍨
ngn
lebih pendek:1↓∊∘.+/0,¨
ngn
yang merupakan 1↓∊0∘.+.,produk inouter - seberapa sering Anda melihat itu :)
ngn
jika saya mengerti benar, ini harus bekerja juga:1<∘≢∩⍥{∊0∘.+.,∪⍭⍵}
ngn
@ ngn Terima kasih. Selesai
Adám
2

05AB1E , 10 8 byte

f€æO`å¦à

-2 byte terima kasih kepada @Emigna .

Cobalah secara online atau verifikasi semua kasus uji .

Penjelasan:

f         # Get all distinct prime factors of both values in the (implicit) input-list
          #  i.e. [2013,2014] → [[3,11,61],[2,19,53]]
 ۾       # Get the powerset for each
          #  → [[[],[3],[11],[3,11],[61],[3,61],[11,61],[3,11,61]],
          #     [[],[2],[19],[2,19],[53],[2,53],[19,53],[2,19,53]]]
   O      # Sum each inner-most list
          #  → [[0,3,11,14,61,64,72,75],[0,2,19,21,53,55,72,74]]
    `     # Push both lists to the stack
     å    # Check for each value in the second list if it's present in the first list
          #  → [1,0,0,0,0,0,1,0]
      ¦   # Remove the first item (since the powerset included empty leading lists)
          #  → [0,0,0,0,0,1,0]
       à  # Check if any are truthy by taking the maximum (which is output implicitly)
          #  → 1
Kevin Cruijssen
sumber
1
f€æO`å¦àharus bekerja untuk 8.
Emigna
1

Python 3 , 206 byte

Ini adalah fungsi lambda (m), yang mengambil dalam 2 angka dan mengembalikan set yang berisi jumlah faktor prima yang sama-sama mereka miliki. Dalam Python ini adalah nilai kebenaran saat tidak kosong, dan nilai falsey saat kosong.

Sunting: Ternyata jawaban asli saya tidak berfungsi untuk input utama, seperti yang ditunjukkan oleh @ JoKing. Ini telah diperbaiki (bersama dengan beberapa bug lain) dengan biaya tragis 40 byte.

q=__import__('itertools').permutations
def p(n):
 i,s=2,set()
 while~-n:
  if n%i:i+=1
  else:n//=i;s|={i}
 return s
s=lambda f:{sum(i)for l in range(1,len(f)+1)for i in q(f,l)}
m=lambda a,b:s(p(a))&s(p(b))

Penjelasan cepat menggunakan komentar:

#Alias for permutations function
q=__import__('itertools').permutations
#Returns set of prime factors of n, including n, if prime
def p(n):
 i,s=2,set()
 while~-n:
  if n%i:i+=1
  else:n//=i;s|={i}
 return s
#Returns all possible sums of 2 or more elements in the given set
s=lambda f:{sum(i)for l in range(1,len(f)+1)for i in q(f,l)}
#Returns any shared possible sums of prime factors of a and b (the intersection of the sets)
m=lambda a,b:s(p(a))&s(p(b))

Cobalah online!

senox13
sumber
Ini tidak berfungsi untuk uji kasus pertama 5,6, karena tidak menangani input utama
Jo King
@ JoKing, terima kasih sudah menangkapnya. Jawaban telah diperbarui.
senox13
1

APL (NARS), 50 char, 100 byte

{⍬≢↑∩/+/¨¨{⍵∼⊂⍬}¨{0=⍴⍵:⊂⍬⋄s,(⊂1⌷⍵),¨s←∇1↓⍵}¨∪¨π¨⍵}

di sini π akan menemukan berbagai faktor pada argumennya;

{0=⍴⍵:⊂⍬⋄s,(⊂1⌷⍵),¨s←∇1↓⍵} 

akan menjadi fungsi yang menemukan semua himpunan bagian ... saya harus mengatakan bahwa tampaknya {⍵operator itsArguments} ¨ (untuk setiap kiri) dan ¨ (untuk setiap kanan) dapat meniru loop dengan jumlah siklus tetap dan ¨¨ ok di untuk melihat himpunan bagian dari satu set ... cara ini tampaknya mengurangi simbol dalam menggambarkan loop ...; uji

  h←{⍬≢↑∩/+/¨¨{⍵∼⊂⍬}¨{0=⍴⍵:⊂⍬⋄s,(⊂1⌷⍵),¨s←∇1↓⍵}¨∪¨π¨⍵}
  h 5 6
1
  h 2013 2014
1
  h 8 15
0
  h 21 25
0

Satu analisis kecil:

π¨⍵  for each arg apply factor 
∪¨ for each arg apply unique
{0=⍴⍵:⊂⍬⋄s,(⊂1⌷⍵),¨s←∇1↓⍵}¨ for each arg apply subsets
{⍵∼⊂⍬}¨ for each argument subtract Zilde enclosed (that would be the void set)
+/¨¨ for each arg (for each arg apply +/)
⍬≢↑∩/ apply intersection, get the first argument and see if it is Zilde (this it is right because enclosed Zilde it seems is the void set)
RosLuP
sumber
1

Japt , 14 byte

®k â ã mx
rf Ê

Disimpan 3 byte berkat @Shaggy

Cobalah

Perwujudan Ketidaktahuan
sumber
Baris kedua bisa ÎfUÌ latau, lebih pendek lagi rf l,. akan menjadi cara terpendek untuk melakukan itu, tetapi Oliver mengalahkan Anda untuk itu.
Shaggy
1

Jelly , 18 9 byte

ÆfŒPḊ§)f/

Cobalah online!

Terima kasih kepada @Jonathan Allan untuk -9 dan bantuan yang luar biasa :).

Mengambil input sebagai array dari dua elemen. Penjelasan kode:

      )    Call Chain 1 for each integer in the input array

ÆfŒPḊ§     Chain 1:
Æf           Compute a list of the prime factors of the integer
  ŒP         Powerset of P, with duplicates and an empty element
    Ḋ        Drop said empty element
     §       Vectorized sum: sum every combination

       f/  Chain 2:
        /    Reduce (the resulting list of two lists of possible sums) by...
       f     ...removing elements to the left that are not in the right

¹

Yang Mulia
sumber
Ambil input sebagai daftar dua nilai dan hindari ,. Itu ẒƇberlebihan, tidak ada faktor prima non-prima. Maka ÆFḢ€ adil Æf, kecuali bahwa yang terakhir memberi kita pengulangan yang mungkin benar-benar kita butuhkan, misalnya 26=2*13dan 125=5*5*5sementara 2+13=5+5+5. Namun dengan itu, tidak cukup baik, misalnya alih-alih 26menggunakan 182=2*7*13yang juga harus menemukan itu 2+13=5+5+5tetapi tidak - sebaliknya kita ingin set-daya ( ŒP) tanpa elemen memimpin, kosong, (kita dapat menggunakan ). S€di sini dapat diganti dengan §. - Anda mungkin dapat menyimpan byte dengan $dan Ɗ-.
Jonathan Allan
Tidak perlu untuk quicks yang saya sebutkan di akhir yang bisa kita gunakan )dan dengan perbaikan saya untuk membuatnya bekerja dengan benar (plus mengganti œ&dengan f) kodenya adalah 9 byte: ÆfŒPḊ§)f/ coba-coba
Jonathan Allan
Diperbarui dengan penjelasan. Terima kasih lagi :)!
Ven
1
Saya memperbarui sedikit penjelasan Anda.
Jonathan Allan
0

Gaia , 16 11 byte

ḍzΣ¦
↑@↑&ỵ!

Cobalah online!

Fungsi teratas (baris pertama) menghitung jumlah dari powerset faktor prima, dan fungsi kedua menemukan jika salah satu elemen dari persimpangan adalah nol.

Giuseppe
sumber