Prime decomposition: Difference between revisions

Content added Content deleted
m (→‎{{header|Wren}}: Minor tidy)
(→‎optimized slightly: ooRexx conformance end corrected output)
Line 5,128: Line 5,128:
A method exists in this REXX program to also test Mersenne-type numbers &nbsp; <big>(2<sup>n</sup> - 1)</big>.
A method exists in this REXX program to also test Mersenne-type numbers &nbsp; <big>(2<sup>n</sup> - 1)</big>.


Since the majority of computing time is spent looking for primes, that part of the program was
Since the majority of computing time is spent looking for primes, that part of the program was
<br>optimized somewhat (but could be extended if more optimization is wanted).
<br>optimized somewhat (but could be extended if more optimization is wanted).
<syntaxhighlight lang="rexx">/*REXX pgm does prime decomposition of a range of positive integers (with a prime count)*/
<syntaxhighlight lang="rexx"></syntaxhighlight>
/*REXX pgm does prime decomposition of a range of positive integers (with a prime count)*/
numeric digits 1000 /*handle thousand digits for the powers*/
parse arg bot top step base add /*get optional arguments from the C.L. */
Numeric Digits 1000 /*handle thousand digits For the powers*/
if bot=='' then do; bot=1; top=100; end /*no BOT given? Then use the default.*/
Parse Arg bot top step base add /*get optional arguments from the C.L. */
If bot='?' Then Do
⚫
if top=='' then top=bot /* " TOP? " " " " " */
Say 'rexx pfoo bot top step base add'
⚫
if step=='' then step= 1 /* " STEP? " " " " " */
Exit
⚫
if add =='' then add= -1 /* " ADD? " " " " " */
End
tell= top>0; top=abs(top) /*if TOP is negative, suppress displays*/
w=length(top) /*get maximum width for aligned display*/
If bot=='' Then /* no arguments given */
Parse Value 1 100 With bot top /* set default range .*/
if base\=='' then w=length(base**top) /*will be testing powers of two later? */
⚫
If top=='' Then top=bot /* process one number */
⚫
@.=left('', 7); @.0="{unity}"; @.1='[prime]' /*some literals: pad; prime (or not).*/
numeric digits max(9, w+1) /*maybe increase the digits precision. */
If step=='' Then step=1 /* step=2 to process only odd numbers */
#=0 /*#: is the number of primes found. */
If add =='' Then add=-1 /* for Mersenne tests */
do n=bot to top by step /*process a single number or a range.*/
tell=top>0 /*If TOP is negative, suppress displays*/
top=abs(top)
?=n; if base\=='' then ?=base**n + add /*should we perform a "Mercenne" test? */
pf=factr(?); f=words(pf) /*get prime factors; number of factors.*/
w=length(top) /*get maximum width For aligned display*/
If base\=='' Then
⚫
if f==1 then #=#+1 /*Is N prime? Then bump prime counter.*/
if tell then say right(?,w) right('('f")",9) 'prime factors: ' @.f pf
w=length(base**top) /*will be testing powers of two later? */
⚫
tag.=left('', 7) /*some literals: pad; prime (or not).*/
⚫
end /*n*/
tag.0='{unity}'
say
tag.1='[prime]'
⚫
ps= 'primes'; if p==1 then ps= "prime" /*setup for proper English in sentence.*/
say right(#, w+9+1) ps 'found.' /*display the number of primes found. */
Numeric Digits max(9,w+1) /*maybe increase the digits precision. */
exit /*stick a fork in it, we're all done. */
np=0 /*np: is the number of primes found.*/
Do n=bot To top by step /*process a single number or a range. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
?=n
⚫
factr: procedure; parse arg x 1 d,$ /*set X, D to argument 1; $ to null.*/
if x==1 then return '' /*handle the special case of X = 1. */
If base\=='' Then /*should we perform a 'Mersenne' test? */
?=base**n+add
do while x//2==0; $=$ 2; x=x%2; end /*append all the 2 factors of new X.*/
do while x//3==0; $=$ 3; x=x%3; end /* " " " 3 " " " " */
pf=factr(?) /* get prime factors */
do while x//5==0; $=$ 5; x=x%5; end /* " " " 5 " " " " */
f=words(pf) /* number of prime factors */
do while x//7==0; $=$ 7; x=x%7; end /* " " " 7 " " " " */
If f=1 Then /* If the number is prime */
/* ___*/
np=np+1 /* Then bump prime counter */
If tell Then
q=1; do while q<=x; q=q*4; end /*these two lines compute integer √ X */
Say right(?,w) right('('f')',9) 'prime factors: ' tag.f pf
r=0; do while q>1; q=q%4; _=d-r-q; r=r%2; if _>=0 then do; d=_; r=r+q; end; end
End /*n*/
Say ''
ps='prime'
⚫
If f>1 Then ps=ps's' /*setup For proper English in sentence.*/
Say right(np, w+9+1) ps 'found.' /*display the number of primes found. */
⚫
Exit /*stick a fork in it, we're all done. */
/*---------------------------------------------------------------------------*/
factr: Procedure
⚫
Parse Arg x 1 d,pl /*set X, D to argument 1, pl to null */
If x==1 Then Return '' /*handle the special case of X=1. */
primes=2 3 5 7
Do While primes>'' /* first check the small primes */
Parse Var primes prime primes
Do While x//prime==0
pl=pl prime
x=x%prime
End
End
r=isqrt(x)
⚫
Do j=11 by 6 To r /*insure that J isn't divisible by 3. */
Parse var j '' -1 _ /*obtain the last decimal digit of J. */
If _\==5 Then Do
⚫
Do While x//j==0
pl=pl j
x=x%j
⚫
End /*maybe reduce by J. */
End
If _ ==3 Then Iterate /*If next Y is divisible by 5? Skip. */
y=j+2
Do While x//y==0
pl=pl y
x=x%y
⚫
End /*maybe reduce by y. */
⚫
End /*j*/


do j=11 by 6 to r /*insure that J isn't divisible by 3.*/
If x==1 Then Return pl /*Is residual=unity? Then don't append.*/
parse var j '' -1 _ /*obtain the last decimal digit of J. */
Return pl x /*return pl with appended residual.*/

if _\==5 then do while x//j==0; $=$ j; x=x%j; end /*maybe reduce by J. */
isqrt: Procedure
⚫
if _ ==3 then iterate /*Is next Y is divisible by 5? Skip.*/
Parse Arg x
y=j+2; do while x//y==0; $=$ y; x=x%y; end /*maybe reduce by J. */
x=abs(x)
⚫
end /*j*/
Parse Value 0 x with lo hi
/* [↓] The $ list has a leading blank.*/
Do While lo<=hi
if x==1 then return $ /*Is residual=unity? Then don't append.*/
t=(lo+hi)%2
return $ x /*return $ with appended residual. */</syntaxhighlight>
If t**2>x Then
hi=t-1
Else
lo=t+1
End
Return t
'''output''' &nbsp; when using the default input of: &nbsp; <tt> 1 &nbsp; 100 </tt>
'''output''' &nbsp; when using the default input of: &nbsp; <tt> 1 &nbsp; 100 </tt>


Line 5,178: Line 5,218:


<pre style="font-size:75%;height:160ex">
<pre style="font-size:75%;height:160ex">

1 (0) prime factors: {unity}
1 (0) prime factors: {unity}
2 (1) prime factors: [prime] 2
2 (1) prime factors: [prime] 2
Line 5,304: Line 5,345:


<pre style="font-size:75%>
<pre style="font-size:75%>

3 (1) prime factors: [prime] 3
3 (1) prime factors: [prime] 3
7 (1) prime factors: [prime] 7
7 (1) prime factors: [prime] 7
Line 5,316: Line 5,358:
4095 (5) prime factors: 3 3 5 7 13
4095 (5) prime factors: 3 3 5 7 13
8191 (1) prime factors: [prime] 8191
8191 (1) prime factors: [prime] 8191
16383 (2) prime factors: 3 5461
16383 (3) prime factors: 3 43 127
32767 (2) prime factors: 7 4681
32767 (3) prime factors: 7 31 151
65535 (4) prime factors: 3 5 17 257
65535 (4) prime factors: 3 5 17 257
131071 (1) prime factors: [prime] 131071
131071 (1) prime factors: [prime] 131071
262143 (5) prime factors: 3 3 3 7 1387
262143 (6) prime factors: 3 3 3 7 19 73
524287 (1) prime factors: [prime] 524287
524287 (1) prime factors: [prime] 524287
1048575 (6) prime factors: 3 5 5 11 41 31
1048575 (6) prime factors: 3 5 5 11 31 41
2097151 (3) prime factors: 7 7 42799
2097151 (4) prime factors: 7 7 127 337
4194303 (4) prime factors: 3 23 89 683
4194303 (4) prime factors: 3 23 89 683
8388607 (2) prime factors: 47 178481
8388607 (2) prime factors: 47 178481
16777215 (7) prime factors: 3 3 5 7 13 17 241
16777215 (7) prime factors: 3 3 5 7 13 17 241
33554431 (1) prime factors: [prime] 33554431
33554431 (3) prime factors: 31 601 1801
67108863 (2) prime factors: 3 22369621
67108863 (3) prime factors: 3 2731 8191
134217727 (2) prime factors: 7 19173961
134217727 (3) prime factors: 7 73 262657
268435455 (5) prime factors: 3 5 29 113 5461
268435455 (6) prime factors: 3 5 29 43 113 127
536870911 (3) prime factors: 233 1103 2089
536870911 (3) prime factors: 233 1103 2089
1073741823 (5) prime factors: 3 3 7 11 1549411
1073741823 (7) prime factors: 3 3 7 11 31 151 331
2147483647 (1) prime factors: [prime] 2147483647
2147483647 (1) prime factors: [prime] 2147483647
4294967295 (5) prime factors: 3 5 17 257 65537
4294967295 (5) prime factors: 3 5 17 257 65537
8589934591 (4) prime factors: 7 23 89 599479
8589934591 (4) prime factors: 7 23 89 599479
17179869183 (3) prime factors: 3 43691 131071
17179869183 (3) prime factors: 3 43691 131071
34359738367 (3) prime factors: 71 122921 3937
34359738367 (4) prime factors: 31 71 127 122921
68719476735 (7) prime factors: 3 3 3 5 7 13 5593771
68719476735 (10) prime factors: 3 3 3 5 7 13 19 37 73 109
137438953471 (1) prime factors: [prime] 137438953471
137438953471 (2) prime factors: 223 616318177
274877906943 (2) prime factors: 3 91625968981
274877906943 (3) prime factors: 3 174763 524287
549755813887 (2) prime factors: 7 78536544841
549755813887 (4) prime factors: 7 79 8191 121369
1099511627775 (7) prime factors: 3 5 5 11 17 41 1912111
1099511627775 (8) prime factors: 3 5 5 11 17 31 41 61681
2199023255551 (2) prime factors: 13367 164511353
2199023255551 (2) prime factors: 13367 164511353
4398046511103 (5) prime factors: 3 3 7 7 9972894583
4398046511103 (8) prime factors: 3 3 7 7 43 127 337 5419
8796093022207 (3) prime factors: 431 9719 2099863
8796093022207 (3) prime factors: 431 9719 2099863
17592186044415 (6) prime factors: 3 5 23 89 683 838861
17592186044415 (7) prime factors: 3 5 23 89 397 683 2113
35184372088831 (2) prime factors: 7 5026338869833
35184372088831 (6) prime factors: 7 31 73 151 631 23311
70368744177663 (4) prime factors: 3 47 178481 2796203
70368744177663 (4) prime factors: 3 47 178481 2796203
140737488355327 (2) prime factors: 2351 59862819377
140737488355327 (3) prime factors: 2351 4513 13264529
281474976710655 (8) prime factors: 3 3 5 7 13 17 257 15732721
281474976710655 (10) prime factors: 3 3 5 7 13 17 97 241 257 673
562949953421311 (1) prime factors: [prime] 562949953421311
562949953421311 (2) prime factors: 127 4432676798593
1125899906842623 (4) prime factors: 3 11 251 135928999981
1125899906842623 (7) prime factors: 3 11 31 251 601 1801 4051


11 primes found.
8 primes found.
</pre>
</pre>
'''output''' &nbsp; when using the input of: &nbsp; <tt> 1 &nbsp; 50 &nbsp; 1 &nbsp; 2 &nbsp; +1 </tt>
'''output''' &nbsp; when using the input of: &nbsp; <tt> 1 &nbsp; 50 &nbsp; 1 &nbsp; 2 &nbsp; +1 </tt>
Line 5,363: Line 5,405:


<pre style="font-size:75%>
<pre style="font-size:75%>

3 (1) prime factors: [prime] 3
3 (1) prime factors: [prime] 3
5 (1) prime factors: [prime] 5
7 (1) prime factors: [prime] 7
9 (2) prime factors: 3 3
15 (2) prime factors: 3 5
17 (1) prime factors: [prime] 17
31 (1) prime factors: [prime] 31
33 (2) prime factors: 3 11
63 (3) prime factors: 3 3 7
65 (2) prime factors: 5 13
127 (1) prime factors: [prime] 127
129 (2) prime factors: 3 43
255 (3) prime factors: 3 5 17
257 (1) prime factors: [prime] 257
511 (2) prime factors: 7 73
513 (4) prime factors: 3 3 3 19
1023 (3) prime factors: 3 11 31
1025 (3) prime factors: 5 5 41
2047 (2) prime factors: 23 89
2049 (2) prime factors: 3 683
4095 (5) prime factors: 3 3 5 7 13
4097 (2) prime factors: 17 241
8191 (1) prime factors: [prime] 8191
8193 (2) prime factors: 3 2731
16383 (3) prime factors: 3 43 127
16385 (3) prime factors: 5 29 113
32767 (3) prime factors: 7 31 151
32769 (4) prime factors: 3 3 11 331
65535 (4) prime factors: 3 5 17 257
65537 (1) prime factors: [prime] 65537
131071 (1) prime factors: [prime] 131071
131073 (2) prime factors: 3 43691
262143 (6) prime factors: 3 3 3 7 19 73
262145 (3) prime factors: 5 13 4033
524287 (1) prime factors: [prime] 524287
524289 (2) prime factors: 3 174763
1048575 (6) prime factors: 3 5 5 11 31 41
1048577 (2) prime factors: 17 61681
2097151 (4) prime factors: 7 7 127 337
2097153 (3) prime factors: 3 3 233017
4194303 (4) prime factors: 3 23 89 683
4194305 (2) prime factors: 5 838861
8388607 (2) prime factors: 47 178481
8388609 (2) prime factors: 3 2796203
16777215 (7) prime factors: 3 3 5 7 13 17 241
16777217 (2) prime factors: 257 65281
33554431 (3) prime factors: 31 601 1801
33554433 (4) prime factors: 3 11 251 4051
67108863 (3) prime factors: 3 2731 8191
67108865 (4) prime factors: 5 53 1613 157
134217727 (3) prime factors: 7 73 262657
134217729 (5) prime factors: 3 3 3 3 1657009
268435455 (6) prime factors: 3 5 29 43 113 127
268435457 (2) prime factors: 17 15790321
536870911 (3) prime factors: 233 1103 2089
536870913 (3) prime factors: 3 59 3033169
1073741823 (7) prime factors: 3 3 7 11 31 151 331
1073741825 (5) prime factors: 5 5 13 41 80581
2147483647 (1) prime factors: [prime] 2147483647
2147483649 (2) prime factors: 3 715827883
4294967295 (5) prime factors: 3 5 17 257 65537
4294967297 (2) prime factors: 641 6700417
8589934591 (4) prime factors: 7 23 89 599479
8589934593 (4) prime factors: 3 3 683 1397419
17179869183 (3) prime factors: 3 43691 131071
17179869185 (4) prime factors: 5 137 953 26317
34359738367 (4) prime factors: 31 71 127 122921
34359738369 (5) prime factors: 3 11 281 86171 43
68719476735 (10) prime factors: 3 3 3 5 7 13 19 37 73 109
68719476737 (2) prime factors: 17 4042322161
137438953471 (2) prime factors: 223 616318177
137438953473 (2) prime factors: 3 45812984491
274877906943 (3) prime factors: 3 174763 524287
274877906945 (2) prime factors: 5 54975581389
549755813887 (4) prime factors: 7 79 8191 121369
549755813889 (3) prime factors: 3 3 61083979321
1099511627775 (8) prime factors: 3 5 5 11 17 31 41 61681
1099511627777 (2) prime factors: 257 4278255361
2199023255551 (2) prime factors: 13367 164511353
2199023255553 (3) prime factors: 3 83 8831418697
4398046511103 (8) prime factors: 3 3 7 7 43 127 337 5419
4398046511105 (5) prime factors: 5 13 29 113 20647621
8796093022207 (3) prime factors: 431 9719 2099863
8796093022209 (2) prime factors: 3 2932031007403
17592186044415 (7) prime factors: 3 5 23 89 397 683 2113
17592186044417 (3) prime factors: 17 353 2931542417
35184372088831 (6) prime factors: 7 31 73 151 631 23311
35184372088833 (5) prime factors: 3 3 3 11 118465899289
70368744177663 (4) prime factors: 3 47 178481 2796203
70368744177665 (4) prime factors: 5 1013 30269 458989
140737488355327 (3) prime factors: 2351 4513 13264529
140737488355329 (2) prime factors: 3 46912496118443
281474976710655 (10) prime factors: 3 3 5 7 13 17 97 241 257 673
281474976710657 (2) prime factors: 65537 4294901761
562949953421311 (2) prime factors: 127 4432676798593
562949953421313 (2) prime factors: 3 187649984473771
1125899906842623 (7) prime factors: 3 11 31 251 601 1801 4051
1125899906842625 (6) prime factors: 5 5 5 41 101 2175126601


5 primes found.
8 primes found.
</pre>
</pre>


Retrieved from "https://rosettacode.org/wiki/Prime_decomposition"