Rosetta Code

Partition an integer x into n primes: Difference between revisions

Page Discussion

Partition an integer x into n primes (view source)

Revision as of 10:51, 8 February 2018

547 bytes added ,  6 years ago
m
Undo revision 259111 by Mdolidon (talk)
m (→‎{{header|J}}: shorten J a bit)
m (Undo revision 259111 by Mdolidon (talk))
Line 297:
<lang j>
load 'format/printf'
 
primes_up_to =: monad def: 'p: i. _1 p: 1 + y'▼
NB. Short J code naturally yields functional solutions. ▼
terms_as_text =: 3 & }. @: ; @: ((' + ' & , @: ":) each "0)
NB. However I don't know of any way to easily make it lazy. ▼
 
NB. When the solution domain is huge, we want to avoid exploring it all.
 
NB. In such a case we can fall back on explicit imperative control strutures.▼
▲NB. ShortSimple, short and clean J code naturally yields functional solutions. and
NB. However this is clearly not where J shines neither with speed nor elegance.▼
▲NB. parallel solutions. However I don't know of any way to easily make it lazy.
NB. make it lazy. Therefore, when the domain solution is huge, even
▲primes_up_to =: monad def 'p: i. _1 p: 1 + y'
NB. though we only want the first solution found, time and space may
terms_as_text =: monad def '; }: , (": each y),.<'' + '''
NB. become a constraint.
▲NB. In such a case we can fall back on explicit imperative control strutures.,
search_next_terms =: dyad define▼
▲NB. Howeverthough this is clearly not where J shines neither with speed nor elegance.
acc=. x NB. -> an accumulator that contains given beginning of the partition.
 
p=. >0{y NB. -> number of elements wanted in the partition
 
ns=. >1{y NB. -> candidate values to be included in the partition
▲search_next_terms as_terms_aux=: dyad define
sum=. >2{y NB. -> the integer to partition
acc=.x
p=.>0{y
ns=.>1{y
sum=.>2{y
 
if. p=1 do.
for_m. i. #ns do.
r =. acc,m{ns
if. sum=+/r do. r return. end.
end.
else.
for_m. i. (#ns)-(p-1) do.
r =. (acc,m{ns) search_next_termsas_terms_aux (p-1);((m+1)}.ns);sum
if. #r do. r return. end.
end.
end.
 
0$0 NB. Empty result if nothing found at the end of this path.
)
 
 
NB. A wrapper with a more pleasant call signature.
NB. Prints a partition of y primes whose sum equals x.▼
as_terms_from=:dyad define
sum=.>0{x
p=.>1{x
ns=.y
(0$0) as_terms_aux p;y;sum
)
 
 
 
▲NB. Prints Finds a partition of y primes, whose sum equals x.
NB. Try 19 in 3 for example.
in =: dyad define
terms =. (0$0x;y) search_next_termsas_terms_from y;(primes_up_to x);x
if. #terms do.
'As the sum of %d primes, %d = %s' printf y;x; terms_as_text terms
Line 338 ⟶ 353:
end.
)
 
 
 
99809 in 1
18 in 2
Line 349 ⟶ 366:
22699 in 4
40355 in 3
</lang>
 
 
{{output}}
<pre>
As the sum of 1 primes, 99809 = 99809
As the sum of 2 primes, 18 = 5 + 13
As the sum of 3 primes, 19 = 3 + 5 + 11
Didn't find a way to express 20 as a sum of 4 different primes.
As the sum of 24 primes, 2017 = 2 + 3 + 5 + 7 + 11 + 13 + 17 + 19 + 23 + 29 + 31 + 37 + 41 + 43 + 47 + 53 + 59 + 61 + 67 + 71 + 73 + 79 + 97 + 1129
As the sum of 1 primes, 22699 = 22699
As the sum of 2 primes, 22699 = 2 + 22697
As the sum of 3 primes, 22699 = 3 + 5 + 22691
As the sum of 4 primes, 22699 = 2 + 3 + 43 + 22651
As the sum of 3 primes, 40355 = 3 + 139 + 40213
</pre>
 
Anonymous user
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/274643"