Rốt cục Các nguyên tố

Gryphon 04/10/2017. 18 answers, 1.017 views
code-golf number sequence primes

Lấy cảm hứng từ rễ kỹ thuật số, gốc nhân tố chính của một số là con số xuất hiện khi bạn lấy các số nguyên tố của một con số, cộng chúng lại với nhau và lặp lại quá trình trên số kết quả, tiếp tục cho đến khi bạn kết thúc với một số nguyên tố mà nó có chính nó như là yếu tố duy nhất của nó, và do đó là rễ nhân tố chính của chính nó). Nguyên tố nhân tố chính của 4 là 4, như 2 * 2 = 2 + 2, và đây là gốc nguyên tố duy nhất không phải nguyên tố của một số nguyên lớn hơn 1 (là một trường hợp đặc biệt, vì nó không có các yếu tố chính). Chuỗi OEIS được hình thành bởi rễ nhân tố nguyên tố là A029908 .

Ví dụ, gốc nhân tố nguyên tố của 24 là:

24=2*2*2*3

2+2+2+3=9=3*3

3+3=6=2*3

2+3=5, and the only prime factor of 5 is 5.  Therefore, the prime factoral root of 24 is 5. 

Nhiệm vụ của bạn:

Viết một chương trình hoặc chức năng tìm nguyên tố gốc nguyên tố của một số nguyên đầu vào.

Đầu vào:

Số nguyên, nhập thông qua bất kỳ phương pháp hợp lý, giữa 2 và số nguyên lớn nhất mà ngôn ngữ của bạn sẽ hỗ trợ (bao gồm). Cụ thể chọn một ngôn ngữ có kích thước số nguyên cực tiểu thấp không hợp lý là không được phép (và cũng vi phạm các lỗ hổng tiêu chuẩn này )

Kết quả:

Một số nguyên, gốc nguyên tố nguyên tố của đầu vào.

Kiểm tra trường hợp:

4   -> 4
24  -> 5
11  -> 11
250 -> 17 

Ghi điểm:

Đây là , điểm số thấp nhất trong byte chiến thắng!

5 Comments
3 scottinet 04/10/2017
Bạn có thể thêm 4 trong các trường hợp thử nghiệm, vì đó là một ngoại lệ và rất dễ quên khi kiểm tra một câu trả lời?
someone 04/10/2017
Chúng ta có phải đầu ra 1 cho 1?
scottinet 04/10/2017
@ một người theo trình tự OEIS được liên kết, nó phải xuất 0 cho 1
2 Martin Ender♦ 04/10/2017
Ai đó thách thức rằng các đầu vào sẽ có ít nhất 2.
Gryphon 05/10/2017
Ai đó xin lỗi vì đã nghỉ một lúc. Như Martin đã nói, thách thức cụ thể nói rằng đầu vào sẽ lớn hơn một, và do đó hành vi khi đầu vào là 1 là undefined.

18 Answers


scottinet 04/10/2017.

05AB1E , 3 byte

FÒO 

Hãy thử trực tuyến!

Explanations:

FÒO   
F    Loops  times + 1
 Ò   List of prime factors w/ duplicates
  O  Total sum of the list
     -- implicit output 
5 comments
Shaggy 04/10/2017
Điều này dường như không thành công cho 4 .
scottinet 04/10/2017
@Shaggy cố định trong khi tiết kiệm 2 byte
8 caird coinheringaahing 04/10/2017
+1 cho mã về cơ bản là FOO
7 steenbergh 04/10/2017
Liệu điều này làm cho bất cứ ai cố gắng để đánh bại một FRAO-máy bay chiến đấu?
Magic Octopus Urn 04/10/2017
Ít nhất nó không phải là FOObar.

Laikoni 05/10/2017.

Haskell , 61 byte

 import Data.Numbers.Primes
until=<<((==)=<<)$sum.primeFactors 

Hãy thử trực tuyến!

Giải trình

until=<<((==)=<<) có một hàm f và áp dụng nó cho đầu vào x cho đến khi đạt đến một điểm cố định, đó là f x bằng x . primeFactors trả về danh sách các yếu tố nguyên tố của một số, sum sản lượng tổng của một danh sách các con số.

But wait, why does until=<<((==)=<<) the job and looks so weird?

Nếu giả sử f=sum.primeFactors , một định nghĩa tự nhiên hơn sẽ là until(\x->f x==x)f , bởi vì until lấy một predicate (một hàm trả về một boolean), một hàm có cùng một đầu vào và kiểu trả về (ví dụ Int -> Int ) và giá trị của kiểu này, và sau đó áp dụng hàm cho giá trị cho đến khi vị từ được hoàn thành.

until(\x->f x==x)f tương tự như until(\x->(==)(f x)x)f , và vì nó cho rằng g (h x) x tương tự như (g=< , chúng ta có được until(\x->((==)=< . Sau khi chuyển đổi Eta , điều này trở nên until((==)=< . Nhưng nếu bây giờ chúng ta xử lý (==)=<< như là một hàm được áp dụng cho f , chúng ta có thể thấy rằng until(((==)=<<)f)f lại có dạng g (h x) x , với g=until , h=((==)=<<)x=f , vì vậy nó có thể được viết lại để (until=<<((==)=<<))f . Sử dụng toán tử $ để loại bỏ các dấu ngoặc ngoài và thay thế f với sum.primeFactors ra giải pháp từ trên.

2 comments
i cri everytim 05/10/2017
=<<((==)=<<)$ Whaaaaaat.
Laikoni 05/10/2017
@ acrieverytim Tôi thêm một lời giải thích. Bạn có thể yêu cầu trong phòng chat Haskell nếu bạn có thêm câu hỏi về phép thuật này hoạt động như thế nào.

Laikoni 04/10/2017.

Husk , 4 byte

ω(Σp 

Hãy thử trực tuyến!

Giải trình:

ω(   -- apply the following function until the result no longer changes (fixpoint)
  Σ  -- sum
   p -- the list of primefactors 

Kevin Cruijssen 05/10/2017.

Java 8, 175 144 142 141 bytes

 n->{for(int i,t=n,x;;n=t){for(i=2;i1|n<5)return n;for(t=0,i=1;i++9;x/=10)t+=x%10;}} 

-1 byte nhờ @Nevay .

Không giống như các byte đơn lẻ trong một số ngôn ngữ chơi golf, Java là khá đầy đủ để kiểm tra chính, yếu tố nguyên tố, số tiền, và như vậy, vì vậy tôi đoán ít hơn 200 không phải là quá tồi tàn.
Có thể vẫn có thể chơi golf bằng cách kết hợp các vòng lặp và không sử dụng một phương pháp đệ quy riêng cho tổng số .

Explanation:

Hãy thử nó ở đây.

 n->{                // Method with integer as both parameter and return-type
  for(int i,        //  Index-integer `i`
          t=n,      //  Temp integer `t`, starting at the input `n`
          x;        //  Temp integer `x`
      ;             //  Loop (1) indefinitely
      n=t){         //    After every iteration, replace `n` with the value `t`
    for(i=2;        //   Reset `i` to 2
        i1          //   If `t` is not 0 (it means it's a prime),
       |n<5)        //   or if `n` is below 5 (for edge-cases `4` and 'prime' `1`)
      return n;     //    Return `n` as result
    for(t=0,        //   Reset `t` to 0
        i=1;        //   Reset `i` to 1
        i++9;    //     Inner loop (5) as long as `x` contains more than 1 digit
            x/=10)  //       After every iteration, remove the trailing digit
          t+=n%10;  //      Increase `t` with the trailing digit of `n`
                    //     End of inner loop (5) (implicit / single-line body)
                    //    End of inner loop (4) (implicit / single-line body)
                    //   End of inner loop (3) (implicit / single-line body)
  }                 //  End of loop (1)
}                   // End of method 
5 comments
3 someone 04/10/2017
+1 cho làm phiền để viết một lời giải thích như verbose như thể đây là một ngôn ngữ golf.
Kevin Cruijssen 04/10/2017
@ ai đó Cảm ơn! Kể từ khi có người hỏi tôi về một giải thích của một câu trả lời Java của tôi một lần trong quá khứ, tôi đã được thêm chúng vào tất cả các câu trả lời của tôi. :)
ETHproductions 04/10/2017
i,t=n,x trông giống như nó thuộc về Python, haha
Kevin Cruijssen 04/10/2017
@ ETHproductions Hehe, quá xấu tôi vẫn phải thêm int hàng đầu (không giống như Python). ;)
Nevay 04/10/2017
Bạn có thể sử dụng i++ thay vì ++i<=n .

someone 04/10/2017.

Jelly , 5 byte

ÆfS$¡ 

Giải thích:

Æf    list of prime factors
  S   sum
   $¡ repeat n times 

Hãy thử trực tuyến!

2 comments
someone 04/10/2017
Cảm ơn. Đã tìm kiếm điều đó trong một thời gian.

Erik the Outgolfer 04/10/2017.

Pyth , 3 bytes

usP 

Hãy thử nó ở đây.

Giải trình:

usPGQ The trailing GQ is implicit
  PG  Get prime factors
 s    Sum
u   Q Repeat until returned value no longer unique starting with the input 

Martin Ender 04/10/2017.

Retina , 30 byte

{+`(\1|\b11+?\B)+$
$1;$#1$*
; 

Đầu vào và đầu ra trong unary .

Hãy thử trực tuyến! (Thực hiện phép chuyển đổi thập phân / đơn nhất cho tiện lợi.)

Giải trình

{+`(\1|\b11+?\B)+$
$1;$#1$* 

{ thị Retina chạy toàn bộ chương trình trong một vòng lặp cho đến khi một sự vượt qua đầy đủ không sửa đổi chuỗi, tức là cho đến khi đạt được một điểm cố định. Do đó, chương trình tự tính toán một bước tổng hợp các yếu tố chính của giá trị hiện tại.

Giai đoạn này tự tính toán yếu tố nguyên tố đầu vào. + Là tương tự như { nhưng chỉ vòng lặp giai đoạn này cho đến khi nó dừng lại thay đổi chuỗi. Regex sẽ cố gắng kết hợp với lần chạy cuối cùng của 1 s bằng cách lặp lại nhiều lần cho cùng một chuỗi con (nghĩa là yếu tố). Cách này được thực hiện là hơi phức tạp do các tài liệu tham khảo về phía trước \1 . Trong lần lặp đầu tiên, nhóm 1 chưa nắm bắt được gì, vì vậy \1 không có điều kiện vô điều kiện. Thay vào đó, chúng ta phải kết hợp \b11+?\B là chuỗi con nhỏ nhất có thể bắt đầu từ khi bắt đầu chạy, chứa ít nhất hai giây và không bao trùm toàn bộ quá trình chạy. Các lần lặp lại tiếp theo sẽ không thể sử dụng phương án này một lần nữa, do \b . Vì vậy, trên tất cả các lặp đi lặp lại, chúng ta đang kết hợp \1 , tức là cùng một chuỗi con lặp đi lặp lại. Quá trình này phải đạt đến cuối chuỗi một cách chính xác ( $ ) để đảm bảo rằng chúng ta đã bắt và ước số thực. Lợi ích của việc sử dụng cách tiếp cận này khá khó khăn là nhóm 1 sẽ được sử dụng chính xác n/d lần, tức là những gì còn lại sau khi chia ra các ước số d .

Chúng tôi thay thế trận đấu này bằng d ( $1 ), một sự tách biệt ;n/d ( $#1$* , trong đó chèn $#1 bản sao của 1 , trong đó $#1 là số lần chụp được thực hiện bởi nhóm 1 ).

Quá trình này dừng lại khi lần chạy cuối cùng trong chuỗi là chính, bởi vì khi đó regex không còn phù hợp nữa.

; 

Tất cả chúng ta cần làm để tổng hợp các số nguyên tố là loại bỏ tất cả các dấu phân cách.


ovs 04/10/2017.

Python 2 , 84 bytes

 f=lambda n,d=2:n>1and(n%d and f(n,d+1)or d+f(n/d))
i=input()
exec'i=f(i);'*i
print i 

Hãy thử trực tuyến!

4 comments
Kevin Cruijssen 04/10/2017
Đây có thể là một câu hỏi khá câm, nhưng làm thế nào để f=lambda n,d=2:n>1and(n%d and f(n,d+1)or d+f(n/d)) làm việc? Tôi đã không bao giờ được lập trình trong Python (chủ yếu là Java và C #), vì vậy tôi không chắc những gì kết quả của chức năng này là. Chức năng này sửa đổi đầu vào n và trả về nó sau đó, hoặc nó tương tự như một boolean trong đó n>1and(n%d and f(n,d+1)or d+f(n/d)) là 0 hoặc 1, hoặc 0 hoặc n , hoặc cái gì khác? Tôi đang cố gắng để hình dung như thế nào một cổng này sẽ giống như trong Java / C #, nhưng tôi không thể bởi vì tôi không thực sự hiểu Python lambdas như thế này nói chung.
1 ovs 04/10/2017
@ KevinCruijssen này tương đương với n>1 ? (n%d!=0 ? f(n, d+1) : d+f(n/d)) : n>1 n>1 ? (n%d!=0 ? f(n, d+1) : d+f(n/d)) : n>1 . Nói chung x and y tương đương với x ? y : x x ? y : x . x and y or z tương đương với x ? y : z x ? y : z trong hầu hết các trường hợp.
1 ovs 04/10/2017
@KevinCruijssen một cổng Java sẽ là một cái gì đó giống như f=(n,d=2)->n>1?n%d>0?f(n,d+1):d+f(n/d):0 .
Kevin Cruijssen 04/10/2017
Ah ok. Cảm ơn đã giải thích, bây giờ nó làm cho nhiều ý nghĩa hơn. Và tôi nhớ x and yx ? y : x x ? y : x từ JavaScript nữa. Cảm ơn!

Mego 04/10/2017.

Trên thực tế , 7 byte

⌠w♂πΣ⌡Y 

Hãy thử trực tuyến!

Giải trình:

⌠w♂πΣ⌡Y
⌠    ⌡Y  do this until output stops changing (fixed-point combinator)
 w         factor into [prime, exponent] pairs
  ♂π       product of each pair
    Σ      sum of products 

Giuseppe 04/10/2017.

R + pracma , 53 byte

 function(n){for(i in 1:n)n=sum(pracma::factors(n))
n} 

Hãy thử trực tuyến! (r-fiddle)

R không có các yếu tố nguyên tố xây dựng, nhưng nhiều gói ( pracma , numbers , vv) làm, vì vậy tôi chọn một thuận tiện ngắn nhất.


Cinaski 05/10/2017.

Ohm v2 , 4 byte

·ΘoΣ 

Hãy thử trực tuyến!

Explanation:

·Θ    evaluate the block until the result returned has already been seen
   Σ  sum
  o   the full prime factorization 

Sherlock9 04/10/2017.

Jelly , 6 byte

Câu trả lời này sử dụng một trong số các nội trang phân tích nguyên tố chính của Jelly và nhanh chóng repeat until the results are no longer unique .

ÆfSµÐL 

Try it online!

4 comments
caird coinheringaahing 04/10/2017
Tôi nghĩ rằng bạn đã được outgolfed nhưng, theo cách tiếp cận của bạn, tôi không chắc chắn cho dù câu trả lời rằng các công trình
Sherlock9 04/10/2017
@ cairdcoinheringaahing Tôi đã chỉ kiểm tra câu trả lời của mình (hoặc đúng hơn, tương đương Python) từ 1 đến 100000 và nó hoạt động. Tôi nghĩ rằng 1 là trường hợp duy nhất, nơi số lượng các bước cần thiết bằng n (đó là tốt, với 1 chúng tôi chỉ cần chạy nó một lần), và có vẻ như không có bất kỳ trường hợp mà số lượng các bước là lớn hơn hơn n (có vẻ như không có bất kỳ counterexamples). Ah tốt, tôi đã outgolfed: D
caird coinheringaahing 04/10/2017
Vâng, nó xảy ra. Mặc dù +1 là chính xác cùng một mã tôi nghĩ khi tôi nhìn thấy thách thức này
Chris 05/10/2017
Tổng các yếu tố nguyên tố của n luôn luôn nhỏ hơn hoặc bằng n, làm cho nó khá dễ dàng để chứng minh rằng n luôn luôn là quá đủ.

Luis Mendo 04/10/2017.

MATL , 6 byte

Sử dụng ý tưởng của scottinet để lặp lại nhiều lần hơn mức cần thiết Cảm ơn Shaggy vì đã chỉ ra một sai lầm, bây giờ sửa lại.

t:"Yfs 

Try it online!

Giải trình

t       % Take input (implicit). Duplicate
:"      % Do the following that many times
  Yf    %   Array of prime factors
  s     %   Sum of array
        % End (implicit). Display (implicit) 
3 comments
Shaggy 04/10/2017
Điều này dường như không thành công cho 4 .
Luis Mendo 04/10/2017
@Shaggy Cảm ơn! Làm việc về điều đó
Luis Mendo 04/10/2017
@Shaggy Giải quyết ngay bây giờ

AdmBorkBork 04/10/2017.

PowerShell , 124 byte

 function f($a){for($i=2;$a-gt1){if(!($a%$i)){$i;$a/=$i}else{$i++}}}
for($x=$args[0];$l-ne$x){$l=$x;$x=(f($x))-join'+'|iex}$x 

Hãy thử trực tuyến!

PowerShell không có bất kỳ yếu tố chính yếu nào tích hợp, do đó, điều này sử dụng mã từ câu trả lời của tôi trên Prime Factors Buddies (dòng trên cùng) để thực hiện tính toán nhân tố.

Dòng thứ hai là phần thịt của chương trình này. Chúng ta lấy đầu vào từ $args thành $x , sau đó for vòng lặp cho đến khi $l-n ot e qual đến $x . (Lần lặp đầu tiên, $l$null$x là số nguyên, vì vậy chúng ta sẽ vòng lặp ít nhất một lần).

Bên trong vòng lặp, chúng ta đặt $l = $x để xác định xem chúng ta đã đạt đến cuối vòng lặp hay không. Sau đó, chúng ta nhận được các yếu tố của $x với f($x) , - -join cùng với +|iex chúng (viết tắt của Invoke-Expression và tương tự như eval ). Đó được lưu trữ trở lại thành $x . Như vậy, chúng ta đã đạt đến "kết thúc", nơi các yếu tố chính tổng kết lại với nhau là trở lại chính nó. Sau đó, chúng ta chỉ đơn giản đặt $x vào đường ống và đầu ra là tiềm ẩn.


user202729 04/10/2017.

Mathematica, 35 byte

#//.x_:>Tr[1##&@@@FactorInteger@x]& 

Hãy thử trực tuyến!

(Toán học không hỗ trợ Tr . Tôi phải thực hiện nó bằng tay)

5 comments
3 Martin Ender♦ 04/10/2017
1##& là viết tắt của TimesFixedPoint gần như luôn luôn được rút ngắn bằng //. : #//.x_:>Tr[1##&@@@FactorInteger@x]&
user202729 04/10/2017
@MartinEnder Cảm ơn! Tôi nên đã biết về Times , nhưng tôi đã không biết về trick FixedPoint .
Jenny_mathy 04/10/2017
Mã của bạn được viết bằng Mathematica. Đây không phải là một chức năng Toán học. Bạn nên thay đổi tên ngôn ngữ thành Mathematica hoặc Tr to Total
user202729 04/10/2017
@ {no one} Xin lỗi, tên ngôn ngữ (Toán học) là một sai lầm. {i cri evritime} cố định điều đó.

Snack 04/10/2017.

Ruby , 63 byte

 ->nNO 

Hãy thử trực tuyến!

Sử dụng cờ -rprime cho +6 byte để sử dụng Prime # prime_division .

prime_division trả về các cặp [prime, exponent] (ví dụ, trong 24 chúng ta có các thừa số [2, 2, 2, 3] vì vậy nó cho [[2, 3], [3, 1]] vì vậy trong mỗi bước chúng ta chỉ nhân các thành viên của những cặp này lại với nhau và tổng kết các kết quả.


Herman Lauenstein 04/10/2017.

Javascript (ES6), 63 byte

 f=n=>(q=(p=(m,x)=>m 
 

Không được nâng cấp:

 f=n=>(                  // Recursive function `f`
    p=(m,x=2)=>(        //   Recursive function `p`, used to sum prime factors
        m 

Kevin Cruijssen 05/10/2017.

Java 8, 101 byte

 n->{for(int i=n;i-->0;n=f(n,2));return n;}int f(int n,int d){return n>1?n%d>0?f(n,d+1):d+f(n/d,2):0;} 

Port of @ovs của Python tuyệt vời 2 câu trả lời .

Explanation:

Hãy thử nó ở đây.

 n->{                  // Method with integer as both parameter and return-type
  for(int i=n;i-->0;  //  Loop the input amount of times
    n=f(n,2)          //   And change `n` that many times with a separate method call
  );                  //  End of loop
  return n;           //  Then return the integer `n` as result
}                     // End of method

int f(int n,int d){   // Separated method with 2 integer parameters and integer return-type
                      // (`d` is 2 when we initially call this recursive-method)
  return n>1?         //  If input `n` is larger than 1:
    n%d>0?            //   And it's not divisible by `d`:
     f(n,d+1)         //    Do a recursive-call with `n, d+1`
    :                 //   Else:
     d                //    Sum `d` with
      +f(n/d,2)       //    a recursive call with `n/d, 2`
   :                  //  Else:
    0;                //   Simply return 0
}                     // End of separated method 

Related questions

Hot questions

Language

Popular Tags