Semiprime: Difference between revisions
Content added Content deleted
(→version 2: added a count of semprimes found, changed comments, source, whitespace, indented the output.) |
|||
| Line 1,367: | Line 1,367: | ||
if bot=='' | bot=="," then bot=random() /*None given? User wants us to guess.*/ |
if bot=='' | bot=="," then bot=random() /*None given? User wants us to guess.*/ |
||
if top=='' | top=="," then top=bot /*maybe define a range of numbers. */ |
if top=='' | top=="," then top=bot /*maybe define a range of numbers. */ |
||
tell= top=>0 | top==bot /*should results be shown to the term? */ |
|||
w=max(length(bot), length(top)) + 5 /*obtain the maximum width of numbers. */ |
|||
numeric digits max(9, w) /*ensure there're enough decimal digits*/ |
numeric digits max(9, w) /*ensure there're enough decimal digits*/ |
||
#=0 /*initialize number of semiprimes found*/ |
|||
do n=bot to abs(top) /*show results for a range of numbers. */ |
|||
?=isSemiPrime(n); #=#+? /*Is N a semiprime?; Maybe bump counter*/ |
|||
if tell then say right(n,w) right(word("isn't" 'is', ?+1), 6) 'semiprime.' |
|||
end /*n*/ |
end /*n*/ |
||
say |
|||
if bot\==top then say 'found ' # " semiprimes." |
|||
exit /*stick a fork in it, we're all done. */ |
exit /*stick a fork in it, we're all done. */ |
||
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
||
| Line 1,394: | Line 1,398: | ||
end /*k*/ /* [↑] see if 2nd factor is prime or ¬*/ |
end /*k*/ /* [↑] see if 2nd factor is prime or ¬*/ |
||
end /*j*/ /* [↑] J is never a multiple of three.*/</lang> |
end /*j*/ /* [↑] J is never a multiple of three.*/</lang> |
||
{{out|output|text= when using the input of: <tt> -1 106 </tt>}} |
|||
<br>(Shown at three-quarter size.) |
|||
<pre style="height: |
<pre style="font-size:75%;height:100ex"> |
||
| ⚫ | |||
-1 isn't semiprime. |
|||
0 isn't semiprime. |
|||
1 isn't semiprime. |
|||
2 isn't semiprime. |
|||
3 isn't semiprime. |
|||
4 is semiprime. |
|||
5 isn't semiprime. |
|||
6 is semiprime. |
|||
7 isn't semiprime. |
|||
8 isn't semiprime. |
|||
9 is semiprime. |
|||
10 is semiprime. |
|||
11 isn't semiprime. |
|||
12 isn't semiprime. |
|||
13 isn't semiprime. |
|||
14 is semiprime. |
|||
15 is semiprime. |
|||
16 isn't semiprime. |
|||
17 isn't semiprime. |
|||
18 isn't semiprime. |
|||
19 isn't semiprime. |
|||
20 isn't semiprime. |
|||
21 is semiprime. |
|||
22 is semiprime. |
|||
23 isn't semiprime. |
|||
24 isn't semiprime. |
|||
25 is semiprime. |
|||
26 is semiprime. |
|||
27 isn't semiprime. |
|||
28 isn't semiprime. |
|||
29 isn't semiprime. |
|||
30 isn't semiprime. |
|||
31 isn't semiprime. |
|||
32 isn't semiprime. |
|||
33 is semiprime. |
|||
34 is semiprime. |
|||
35 is semiprime. |
|||
36 isn't semiprime. |
|||
37 isn't semiprime. |
|||
38 is semiprime. |
|||
39 is semiprime. |
|||
40 isn't semiprime. |
|||
41 isn't semiprime. |
|||
42 isn't semiprime. |
|||
43 isn't semiprime. |
|||
44 isn't semiprime. |
|||
45 isn't semiprime. |
|||
46 is semiprime. |
|||
47 isn't semiprime. |
|||
48 isn't semiprime. |
|||
49 is semiprime. |
|||
50 isn't semiprime. |
|||
51 is semiprime. |
|||
52 isn't semiprime. |
|||
53 isn't semiprime. |
|||
54 isn't semiprime. |
|||
55 is semiprime. |
|||
56 isn't semiprime. |
|||
57 is semiprime. |
|||
58 is semiprime. |
|||
59 isn't semiprime. |
|||
60 isn't semiprime. |
|||
61 isn't semiprime. |
|||
62 is semiprime. |
|||
63 isn't semiprime. |
|||
64 isn't semiprime. |
|||
65 is semiprime. |
|||
66 isn't semiprime. |
|||
67 isn't semiprime. |
|||
68 isn't semiprime. |
|||
69 is semiprime. |
|||
70 isn't semiprime. |
|||
71 isn't semiprime. |
|||
72 isn't semiprime. |
|||
73 isn't semiprime. |
|||
74 is semiprime. |
|||
75 isn't semiprime. |
|||
76 isn't semiprime. |
|||
77 is semiprime. |
|||
78 isn't semiprime. |
|||
79 isn't semiprime. |
|||
80 isn't semiprime. |
|||
81 isn't semiprime. |
|||
82 is semiprime. |
|||
83 isn't semiprime. |
|||
84 isn't semiprime. |
|||
85 is semiprime. |
|||
86 is semiprime. |
|||
87 is semiprime. |
|||
88 isn't semiprime. |
|||
89 isn't semiprime. |
|||
90 isn't semiprime. |
|||
91 is semiprime. |
|||
92 isn't semiprime. |
|||
93 is semiprime. |
|||
94 is semiprime. |
|||
95 is semiprime. |
|||
96 isn't semiprime. |
|||
97 isn't semiprime. |
|||
98 isn't semiprime. |
|||
99 isn't semiprime. |
|||
100 isn't semiprime. |
|||
101 isn't semiprime. |
|||
102 isn't semiprime. |
|||
103 isn't semiprime. |
|||
104 isn't semiprime. |
|||
105 isn't semiprime. |
|||
106 is semiprime. |
|||
found 35 semiprimes. |
|||
</pre> |
</pre> |
||
{{out|output|text= when using the input of: <tt> 99888111555 99888111600 </tt>}} |
|||
<br>(Shown at three-quarter size.) |
|||
<pre style="height: |
<pre style="font-size:75%;height:100ex"> |
||
99888111555 isn't semiprime. |
|||
99888111555 isn't semiprime. |
|||
99888111556 isn't semiprime. |
|||
99888111557 isn't semiprime. |
|||
99888111558 isn't semiprime. |
|||
99888111559 isn't semiprime. |
|||
99888111560 isn't semiprime. |
|||
99888111561 isn't semiprime. |
|||
99888111562 isn't semiprime. |
|||
99888111563 is semiprime. |
|||
99888111564 isn't semiprime. |
|||
99888111565 isn't semiprime. |
|||
99888111566 is semiprime. |
|||
99888111567 isn't semiprime. |
|||
99888111568 isn't semiprime. |
|||
99888111569 is semiprime. |
|||
99888111570 isn't semiprime. |
|||
99888111571 isn't semiprime. |
|||
99888111572 isn't semiprime. |
|||
99888111573 isn't semiprime. |
|||
99888111574 is semiprime. |
|||
99888111575 isn't semiprime. |
|||
99888111576 isn't semiprime. |
|||
99888111577 isn't semiprime. |
|||
99888111578 is semiprime. |
|||
99888111579 isn't semiprime. |
|||
99888111580 isn't semiprime. |
|||
99888111581 isn't semiprime. |
|||
99888111582 isn't semiprime. |
|||
99888111583 isn't semiprime. |
|||
99888111584 isn't semiprime. |
|||
99888111585 isn't semiprime. |
|||
99888111586 isn't semiprime. |
|||
99888111587 isn't semiprime. |
|||
99888111588 isn't semiprime. |
|||
99888111589 isn't semiprime. |
|||
99888111590 isn't semiprime. |
|||
99888111591 is semiprime. |
|||
99888111592 isn't semiprime. |
|||
99888111593 is semiprime. |
|||
99888111594 isn't semiprime. |
|||
99888111595 isn't semiprime. |
|||
99888111596 isn't semiprime. |
|||
99888111597 isn't semiprime. |
|||
99888111598 isn't semiprime. |
|||
99888111599 isn't semiprime. |
|||
| ⚫ | |||
found 7 semiprimes. |
|||
</pre> |
</pre> |
||
===version 3, with memoization=== |
|||
This REXX version is overt 20% faster than version 2   (when in the ''millions'' range). |
|||
If the 2<sup>nd</sup> argument ('''top''') is negative (it's absolute value is used), individual numbers in the range aren't shown, but the count of semiprimes found is shown. |
|||
It gets its speed increase by the use of memoization of the prime numbers found, and other speed improvements. |
|||
<lang rexx>/*REXX program determines if any integer (or a range of integers) is/are semiprime. */ |
|||
parse arg bot top . /*obtain optional arguments from the CL*/ |
|||
if bot=='' | bot=="," then bot=random() /*None given? User wants us to guess.*/ |
|||
if top=='' | top=="," then top=bot /*maybe define a range of numbers. */ |
|||
tell= bot=>0 & top=>0 /*should results be shown to the term? */ |
|||
w=max(length(bot), length(top)) /*obtain the maximum width of numbers. */ |
|||
!.=; !.2=1; !.3=1; !.5=1; !.7=1; !.11=1; !.13=1; !.17=1; !.19=1; !.23=1; !.29=1; !.31=1 |
|||
numeric digits max(9, w) /*ensure there're enough decimal digits*/ |
|||
#=0 /*initialize number of semiprimes found*/ |
|||
do n=abs(bot) to abs(top) /*show results for a range of numbers. */ |
|||
?=isSemiPrime(n); #=#+? /*Is N a semiprime?; Maybe bump counter*/ |
|||
if tell then say right(n,w) right(word("isn't" 'is', ?+1), 6) 'semiprime.' |
|||
end /*n*/ |
|||
say |
|||
if bot\==top then say 'found ' # " semiprimes." |
|||
exit /*stick a fork in it, we're all done. */ |
|||
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
|||
isPrime: procedure expose !.; parse arg x; if x<2 then return 0 /*number too low?*/ |
|||
if !.x==1 then return 1 /*a known prime. */ |
|||
if x// 2==0 then return 0; if x//3==0 then return 0 /*÷ by 2;÷by 3?*/ |
|||
parse var x '' -1 _; if _==5 then return 0 /*last digit a 5?*/ |
|||
if x// 7==0 then return 0; if x//11==0 then return 0 /*÷ by 7;÷by 11?*/ |
|||
if x//13==0 then return 0; if x//17==0 then return 0 /*÷ by 13;÷by 17?*/ |
|||
if x//19==0 then return 0; if x//23==0 then return 0 /*÷ by 19;÷by 23?*/ |
|||
do j=29 by 6 until j*j>x; if x//j==0 then return 0 /*not a prime. */ |
|||
if x//(j+2)==0 then return 0 /* " " " */ |
|||
end /*j*/ |
|||
!.x=1; return 1 /*indicate that X is a prime number. */ |
|||
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
|||
isSemiPrime: procedure expose !.; parse arg x; if x<4 then return 0 |
|||
do i=2 for 2; if x//i==0 then if isPrime(x%i) then return 1 |
|||
else return 0 |
|||
end /*i*/ |
|||
/* ___ */ |
|||
do j=5 by 6 until j*j>x /* > √ x ?*/ |
|||
do k=j by 2 for 2; if x//k==0 then if isPrime(x%k) then return 1 |
|||
else return 0 |
|||
end /*k*/ /* [↑] see if 2nd factor is prime or ¬*/ |
|||
end /*j*/ /* [↑] J is never a multiple of three.*/ |
|||
return 0</lang> |
|||
{{out|output|text= is identical to the previous REXX version.}} <br><br> |
|||
=={{header|Ring}}== |
=={{header|Ring}}== |
||