Semiprime: Difference between revisions
Content added Content deleted
mNo edit summary |
m (→version 2: added/changed comments and whitespace, changed indentations.) |
||
| Line 1,245: | Line 1,245: | ||
===version 2=== |
===version 2=== |
||
The method used is to examine |
The method used is to examine integers, skipping primes. |
||
If it's composite (the 1<sup>st</sup> factor is prime), then check if the 2<sup>nd</sup> factor is prime. If so, the number is a semiprime. |
If it's composite (the 1<sup>st</sup> factor is prime), then check if the 2<sup>nd</sup> factor is prime. If so, the number is a ''semiprime''. |
||
The '''isPrime''' function could be optimized by utilizing an integer square root function instead of testing if '''j*j>x''' for every divisor. |
The '''isPrime''' function could be optimized by utilizing an integer square root function instead of testing if '''j*j>x''' for every divisor. |
||
<lang rexx>/*REXX program determines if any |
<lang rexx>/*REXX program determines if any integer (or a range of integers) is/are semiprime. */ |
||
parse arg bot top . /*obtain optional |
parse arg bot top . /*obtain optional arguments from the CL*/ |
||
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. */ |
||
w=max(length(bot), length(top)) /*obtain the maximum width of numbers. */ |
w=max(length(bot), length(top)) /*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*/ |
||
do n=bot to top /*show results for a range of numbers. */ |
do n=bot to top /*show results for a range of numbers. */ |
||
if isSemiPrime(n) then say right(n,w) " is semiprime." |
if isSemiPrime(n) then say right(n, w) " is semiprime." |
||
else say right(n,w) " isn't semiprime." |
else say right(n, w) " isn't semiprime." |
||
end /*n*/ |
end /*n*/ |
||
exit /*stick a fork in it, we're all done. */ |
exit /*stick a fork in it, we're all done. */ |
||
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
|||
/*────────────────────────────────────────────────────────────────────────────*/ |
|||
isPrime: procedure; parse arg x; if x<2 then return 0 |
isPrime: procedure; parse arg x; if x<2 then return 0 /*number too low?*/ |
||
if wordpos(x, '2 3 5 7 11 13 17 19 23')\==0 then return 1 |
if wordpos(x, '2 3 5 7 11 13 17 19 23')\==0 then return 1 /*it's low prime.*/ |
||
if x//2==0 then return 0; if x//3==0 then return 0 |
if x//2==0 then return 0; if x//3==0 then return 0 /*÷ by 2; ÷ by 3?*/ |
||
do j=5 by 6 until j*j>x; if x//j==0 then return 0 |
do j=5 by 6 until j*j>x; if x//j==0 then return 0 /*not a prime. */ |
||
if x//(j+2)==0 then return 0 |
if x//(j+2)==0 then return 0 /* " " " */ |
||
end /*j*/ |
end /*j*/ |
||
return 1 /*indicate that X is a prime number. */ |
return 1 /*indicate that X is a prime number. */ |
||
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
|||
/*────────────────────────────────────────────────────────────────────────────*/ |
|||
isSemiPrime: procedure; parse arg x; |
isSemiPrime: procedure; parse arg x; if x<4 then return 0 |
||
x=x/1 |
|||
do i=2 for 2; if x//i==0 then |
do i=2 for 2; if x//i==0 then if isPrime(x%i) then return 1 |
||
else return 0 |
else return 0 |
||
end /*i*/ |
end /*i*/ |
||
/* ___ */ |
/* ___ */ |
||
do j=5 by 6; if j*j>x then return 0 |
do j=5 by 6; if j*j>x then return 0 /* > √ x ?*/ |
||
do k=j by 2 for 2; if x//k==0 then if isPrime(x%k) then return 1 |
do k=j by 2 for 2; if x//k==0 then if isPrime(x%k) then return 1 |
||
else return 0 |
else return 0 |
||
end /*k*/ |
end /*k*/ /* [↑] see if 2nd factor is prime or ¬*/ |
||
end /*j*/ |
end /*j*/ /* [↑] J is never a multiple of three.*/</lang> |
||
'''output''' when the input |
'''output''' when using the input of: <tt> -1 106 </tt> |
||
<pre style="height:44ex"> |
<pre style="height:44ex"> |
||
-1 isn't semiprime. |
-1 isn't semiprime. |
||
| Line 1,392: | Line 1,392: | ||
106 is semiprime. |
106 is semiprime. |
||
</pre> |
</pre> |
||
'''output''' when the input |
'''output''' when using the input of: <tt> 99888111555 99888111600 </tt> |
||
<pre style="height:44ex"> |
<pre style="height:44ex"> |
||
99888111555 isn't semiprime. |
99888111555 isn't semiprime. |
||