Semiprime: Difference between revisions
Content added Content deleted
(→{{header|PHP}}: Added.) |
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
||
Line 32: | Line 32: | ||
{{trans|C++}} |
{{trans|C++}} |
||
< |
<syntaxhighlight lang="11l">F is_semiprime(=c) |
||
V a = 2 |
V a = 2 |
||
V b = 0 |
V b = 0 |
||
Line 43: | Line 43: | ||
R b == 2 |
R b == 2 |
||
print((1..100).filter(n -> is_semiprime(n)))</ |
print((1..100).filter(n -> is_semiprime(n)))</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 52: | Line 52: | ||
=={{header|360 Assembly}}== |
=={{header|360 Assembly}}== |
||
{{trans|C}} |
{{trans|C}} |
||
< |
<syntaxhighlight lang="360asm">* Semiprime 14/03/2017 |
||
SEMIPRIM CSECT |
SEMIPRIM CSECT |
||
USING SEMIPRIM,R13 base register |
USING SEMIPRIM,R13 base register |
||
Line 122: | Line 122: | ||
XDEC DS CL12 temp |
XDEC DS CL12 temp |
||
YREGS |
YREGS |
||
END SEMIPRIM</ |
END SEMIPRIM</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 132: | Line 132: | ||
=={{header|Action!}}== |
=={{header|Action!}}== |
||
< |
<syntaxhighlight lang="action!">BYTE FUNC IsSemiPrime(INT n) |
||
INT a,b |
INT a,b |
||
Line 159: | Line 159: | ||
FI |
FI |
||
OD |
OD |
||
RETURN</ |
RETURN</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Semiprime.png Screenshot from Atari 8-bit computer] |
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Semiprime.png Screenshot from Atari 8-bit computer] |
||
Line 175: | Line 175: | ||
This imports the package '''Prime_Numbers''' from [[Prime decomposition#Ada]]. |
This imports the package '''Prime_Numbers''' from [[Prime decomposition#Ada]]. |
||
< |
<syntaxhighlight lang="ada">with Prime_Numbers, Ada.Text_IO; |
||
procedure Test_Semiprime is |
procedure Test_Semiprime is |
||
Line 195: | Line 195: | ||
end if; |
end if; |
||
end loop; |
end loop; |
||
end Test_Semiprime;</ |
end Test_Semiprime;</syntaxhighlight> |
||
It outputs all semiprimes below 100 and all semiprimes between 1675 and 1680: |
It outputs all semiprimes below 100 and all semiprimes between 1675 and 1680: |
||
Line 212: | Line 212: | ||
=={{header|ALGOL 68}}== |
=={{header|ALGOL 68}}== |
||
< |
<syntaxhighlight lang="algol68"># returns TRUE if n is semi-prime, FALSE otherwise # |
||
# n is semi prime if it has exactly two prime factors # |
# n is semi prime if it has exactly two prime factors # |
||
PROC is semiprime = ( INT n )BOOL: |
PROC is semiprime = ( INT n )BOOL: |
||
Line 250: | Line 250: | ||
OD; |
OD; |
||
print( ( newline ) ) |
print( ( newline ) ) |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 259: | Line 259: | ||
=={{header|Arturo}}== |
=={{header|Arturo}}== |
||
< |
<syntaxhighlight lang="rebol">semiPrime?: function [x][ |
||
2 = size factors.prime x |
2 = size factors.prime x |
||
] |
] |
||
print select 1..100 => semiPrime?</ |
print select 1..100 => semiPrime?</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 271: | Line 271: | ||
=={{header|AutoHotkey}}== |
=={{header|AutoHotkey}}== |
||
{{works with|AutoHotkey_L}} |
{{works with|AutoHotkey_L}} |
||
< |
<syntaxhighlight lang="autohotkey">SetBatchLines -1 |
||
k := 1 |
k := 1 |
||
loop, 100 |
loop, 100 |
||
Line 325: | Line 325: | ||
} |
} |
||
;================================================================================================================================================= |
;================================================================================================================================================= |
||
esc::Exitapp</ |
esc::Exitapp</syntaxhighlight> |
||
{{output}} |
{{output}} |
||
<Pre> |
<Pre> |
||
Line 336: | Line 336: | ||
=={{header|AWK}}== |
=={{header|AWK}}== |
||
<syntaxhighlight lang="awk"> |
|||
<lang AWK> |
|||
# syntax: GAWK -f SEMIPRIME.AWK |
# syntax: GAWK -f SEMIPRIME.AWK |
||
BEGIN { |
BEGIN { |
||
Line 365: | Line 365: | ||
return(nf == 2) |
return(nf == 2) |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 376: | Line 376: | ||
==={{header|ASIC}}=== |
==={{header|ASIC}}=== |
||
{{trans|Tiny BASIC}} |
{{trans|Tiny BASIC}} |
||
< |
<syntaxhighlight lang="basic"> |
||
REM Semiprime |
REM Semiprime |
||
PRINT "Enter an integer "; |
PRINT "Enter an integer "; |
||
Line 400: | Line 400: | ||
ENDIF |
ENDIF |
||
END |
END |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 412: | Line 412: | ||
==={{header|BASIC256}}=== |
==={{header|BASIC256}}=== |
||
< |
<syntaxhighlight lang="basic256">function semiprime$ (n) |
||
a = 2 |
a = 2 |
||
c = 0 |
c = 0 |
||
Line 430: | Line 430: | ||
print i, semiprime$(i) |
print i, semiprime$(i) |
||
next i |
next i |
||
end</ |
end</syntaxhighlight> |
||
==={{header|FreeBASIC}}=== |
==={{header|FreeBASIC}}=== |
||
< |
<syntaxhighlight lang="freebasic">function semiprime( n as uinteger ) as boolean |
||
dim as uinteger a = 2, c = 0 |
dim as uinteger a = 2, c = 0 |
||
while c < 3 andalso n > 1 |
while c < 3 andalso n > 1 |
||
Line 449: | Line 449: | ||
for i as uinteger = 0 to 64 |
for i as uinteger = 0 to 64 |
||
print i, semiprime(i) |
print i, semiprime(i) |
||
next i</ |
next i</syntaxhighlight> |
||
==={{header|GW-BASIC}}=== |
==={{header|GW-BASIC}}=== |
||
< |
<syntaxhighlight lang="gwbasic">10 INPUT "Enter a number: ", N |
||
20 N=ABS(N) |
20 N=ABS(N) |
||
30 C = 0 |
30 C = 0 |
||
Line 459: | Line 459: | ||
60 IF N MOD F = 0 THEN C = C + 1 : N = N / F ELSE F = F + 1 |
60 IF N MOD F = 0 THEN C = C + 1 : N = N / F ELSE F = F + 1 |
||
70 IF N > 1 THEN GOTO 60 |
70 IF N > 1 THEN GOTO 60 |
||
80 IF C=2 THEN PRINT "It's a semiprime." ELSE PRINT "It is not a semiprime."</ |
80 IF C=2 THEN PRINT "It's a semiprime." ELSE PRINT "It is not a semiprime."</syntaxhighlight> |
||
==={{header|Minimal BASIC}}=== |
==={{header|Minimal BASIC}}=== |
||
Line 465: | Line 465: | ||
{{works with|Commodore BASIC|3.5}} |
{{works with|Commodore BASIC|3.5}} |
||
{{works with|Nascom ROM BASIC|4.7}} |
{{works with|Nascom ROM BASIC|4.7}} |
||
< |
<syntaxhighlight lang="gwbasic"> |
||
10 REM Semiprime |
10 REM Semiprime |
||
20 PRINT "Enter an integer"; |
20 PRINT "Enter an integer"; |
||
Line 483: | Line 483: | ||
160 PRINT "It is not a semiprime." |
160 PRINT "It is not a semiprime." |
||
170 END |
170 END |
||
</syntaxhighlight> |
|||
</lang> |
|||
==={{header|PureBasic}}=== |
==={{header|PureBasic}}=== |
||
< |
<syntaxhighlight lang="purebasic">Procedure.s semiprime(n.i) |
||
a.i = 2 |
a.i = 2 |
||
c.i = 0 |
c.i = 0 |
||
Line 510: | Line 510: | ||
PrintN(#CRLF$ + "--- terminado, pulsa RETURN---"): Input() |
PrintN(#CRLF$ + "--- terminado, pulsa RETURN---"): Input() |
||
CloseConsole() |
CloseConsole() |
||
End</ |
End</syntaxhighlight> |
||
==={{header|Tiny BASIC}}=== |
==={{header|Tiny BASIC}}=== |
||
< |
<syntaxhighlight lang="tinybasic"> PRINT "Enter an integer" |
||
INPUT N |
INPUT N |
||
IF N < 0 THEN LET N = -N |
IF N < 0 THEN LET N = -N |
||
Line 528: | Line 528: | ||
30 LET C = C + 1 |
30 LET C = C + 1 |
||
LET N = N / F |
LET N = N / F |
||
GOTO 10</ |
GOTO 10</syntaxhighlight> |
||
==={{header|Yabasic}}=== |
==={{header|Yabasic}}=== |
||
< |
<syntaxhighlight lang="yabasic">sub semiprime$ (n) |
||
a = 2 |
a = 2 |
||
c = 0 |
c = 0 |
||
Line 549: | Line 549: | ||
print i, chr$(9), semiprime$(i) |
print i, chr$(9), semiprime$(i) |
||
next i |
next i |
||
end</ |
end</syntaxhighlight> |
||
=={{header|Bracmat}}== |
=={{header|Bracmat}}== |
||
When Bracmat is asked to take the square (or any other) root of a number, it does so by first finding the number's prime factors. It can do that for numbers up to 2^32 or 2^64 (depending on compiler and processor). |
When Bracmat is asked to take the square (or any other) root of a number, it does so by first finding the number's prime factors. It can do that for numbers up to 2^32 or 2^64 (depending on compiler and processor). |
||
< |
<syntaxhighlight lang="bracmat">semiprime= |
||
m n a b |
m n a b |
||
. 2^-64:?m |
. 2^-64:?m |
||
Line 559: | Line 559: | ||
& !arg^!m |
& !arg^!m |
||
: (#%?a^!m*#%?b^!m|#%?a^!n&!a:?b) |
: (#%?a^!m*#%?b^!m|#%?a^!n&!a:?b) |
||
& (!a.!b);</ |
& (!a.!b);</syntaxhighlight> |
||
Test with numbers < 2^63: |
Test with numbers < 2^63: |
||
< |
<syntaxhighlight lang="bracmat"> 2^63:?u |
||
& whl |
& whl |
||
' ( -1+!u:>2:?u |
' ( -1+!u:>2:?u |
||
Line 568: | Line 568: | ||
| |
| |
||
) |
) |
||
);</ |
);</syntaxhighlight> |
||
Output: |
Output: |
||
Line 619: | Line 619: | ||
=={{header|C}}== |
=={{header|C}}== |
||
< |
<syntaxhighlight lang="c">#include <stdio.h> |
||
int semiprime(int n) |
int semiprime(int n) |
||
Line 639: | Line 639: | ||
return 0; |
return 0; |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> 4 6 9 10 14 15 21 22 25 26 33 34 35 38 39 46 49 51 55 57 58 62 65 69 74 77 82 85 86 87 91 93 94 95</pre> |
<pre> 4 6 9 10 14 15 21 22 25 26 33 34 35 38 39 46 49 51 55 57 58 62 65 69 74 77 82 85 86 87 91 93 94 95</pre> |
||
=={{header|C sharp|C#}}== |
=={{header|C sharp|C#}}== |
||
< |
<syntaxhighlight lang="csharp"> |
||
static void Main(string[] args) |
static void Main(string[] args) |
||
{ |
{ |
||
Line 673: | Line 673: | ||
return b == 2; |
return b == 2; |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 729: | Line 729: | ||
=={{header|C++}}== |
=={{header|C++}}== |
||
< |
<syntaxhighlight lang="cpp"> |
||
#include <iostream> |
#include <iostream> |
||
Line 751: | Line 751: | ||
return 0; |
return 0; |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 759: | Line 759: | ||
=={{header|Clojure}}== |
=={{header|Clojure}}== |
||
{{trans|C}} |
{{trans|C}} |
||
< |
<syntaxhighlight lang="lisp"> |
||
(ns example |
(ns example |
||
(:gen-class)) |
(:gen-class)) |
||
Line 774: | Line 774: | ||
(println (filter semi-prime? (range 1 100))) |
(println (filter semi-prime? (range 1 100))) |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{Out}} |
{{Out}} |
||
<pre> |
<pre> |
||
Line 781: | Line 781: | ||
=={{header|Common Lisp}}== |
=={{header|Common Lisp}}== |
||
< |
<syntaxhighlight lang="lisp">(defun semiprimep (n &optional (a 2)) |
||
(cond ((> a (isqrt n)) nil) |
(cond ((> a (isqrt n)) nil) |
||
((zerop (rem n a)) (and (primep a) (primep (/ n a)))) |
((zerop (rem n a)) (and (primep a) (primep (/ n a)))) |
||
Line 789: | Line 789: | ||
(cond ((> a (isqrt n)) t) |
(cond ((> a (isqrt n)) t) |
||
((zerop (rem n a)) nil) |
((zerop (rem n a)) nil) |
||
(t (primep n (+ a 1)))))</ |
(t (primep n (+ a 1)))))</syntaxhighlight> |
||
Example Usage: |
Example Usage: |
||
Line 800: | Line 800: | ||
=={{header|Crystal}}== |
=={{header|Crystal}}== |
||
{{trans|D}} |
{{trans|D}} |
||
< |
<syntaxhighlight lang="ruby">def semiprime(n) |
||
nf = 0 |
nf = 0 |
||
(2..n).each do |i| |
(2..n).each do |i| |
||
Line 812: | Line 812: | ||
end |
end |
||
(1675..1681).each { |n| puts "#{n} -> #{semiprime(n)}" }</ |
(1675..1681).each { |n| puts "#{n} -> #{semiprime(n)}" }</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>1675 -> false |
<pre>1675 -> false |
||
Line 823: | Line 823: | ||
Faster version using 'factor' function from [U|Li]nux Core Utilities library. |
Faster version using 'factor' function from [U|Li]nux Core Utilities library. |
||
< |
<syntaxhighlight lang="ruby">def semiprime(n) |
||
`factor #{n}`.split(' ').size == 3 |
`factor #{n}`.split(' ').size == 3 |
||
end |
end |
||
n = 0xffffffffffffffff_u64 # 2**64 - 1 = 18446744073709551615 |
n = 0xffffffffffffffff_u64 # 2**64 - 1 = 18446744073709551615 |
||
(n-50..n).each { |n| puts "#{n} -> #{semiprime(n)}" }</ |
(n-50..n).each { |n| puts "#{n} -> #{semiprime(n)}" }</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>18446744073709551565 -> false |
<pre>18446744073709551565 -> false |
||
Line 883: | Line 883: | ||
=={{header|D}}== |
=={{header|D}}== |
||
{{trans|Go}} |
{{trans|Go}} |
||
< |
<syntaxhighlight lang="d">bool semiprime(long n) pure nothrow @safe @nogc { |
||
auto nf = 0; |
auto nf = 0; |
||
foreach (immutable i; 2 .. n + 1) { |
foreach (immutable i; 2 .. n + 1) { |
||
Line 901: | Line 901: | ||
foreach (immutable n; 1675 .. 1681) |
foreach (immutable n; 1675 .. 1681) |
||
writeln(n, " -> ", n.semiprime); |
writeln(n, " -> ", n.semiprime); |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>1675 -> false |
<pre>1675 -> false |
||
Line 912: | Line 912: | ||
=={{header|DCL}}== |
=={{header|DCL}}== |
||
Given a file primes.txt is the list of primes up to the sqrt(2^31-1), i.e. 46337; |
Given a file primes.txt is the list of primes up to the sqrt(2^31-1), i.e. 46337; |
||
< |
<syntaxhighlight lang="dcl">$ p1 = f$integer( p1 ) |
||
$ if p1 .lt. 2 |
$ if p1 .lt. 2 |
||
$ then |
$ then |
||
Line 959: | Line 959: | ||
$ |
$ |
||
$ clean: |
$ clean: |
||
$ close primes</ |
$ close primes</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>$ @factor 6 |
<pre>$ @factor 6 |
||
Line 971: | Line 971: | ||
=={{header|EchoLisp}}== |
=={{header|EchoLisp}}== |
||
< |
<syntaxhighlight lang="scheme"> |
||
(lib 'math) |
(lib 'math) |
||
(define (semi-prime? n) |
(define (semi-prime? n) |
||
Line 992: | Line 992: | ||
(prime-factors 100000000042) |
(prime-factors 100000000042) |
||
→ (2 50000000021) |
→ (2 50000000021) |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Elixir}}== |
=={{header|Elixir}}== |
||
< |
<syntaxhighlight lang="elixir">defmodule Prime do |
||
def semiprime?(n), do: length(decomposition(n)) == 2 |
def semiprime?(n), do: length(decomposition(n)) == 2 |
||
Line 1,008: | Line 1,008: | ||
Enum.each(1675..1680, fn n -> |
Enum.each(1675..1680, fn n -> |
||
:io.format "~w -> ~w\t~s~n", [n, Prime.semiprime?(n), Prime.decomposition(n)|>Enum.join(" x ")] |
:io.format "~w -> ~w\t~s~n", [n, Prime.semiprime?(n), Prime.decomposition(n)|>Enum.join(" x ")] |
||
end)</ |
end)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,025: | Line 1,025: | ||
Another using prime factors from [[Prime_decomposition#Erlang]] : |
Another using prime factors from [[Prime_decomposition#Erlang]] : |
||
< |
<syntaxhighlight lang="erlang"> |
||
-module(factors). |
-module(factors). |
||
-export([factors/1,kthfactor/2]). |
-export([factors/1,kthfactor/2]). |
||
Line 1,045: | Line 1,045: | ||
_ -> |
_ -> |
||
false end. |
false end. |
||
</syntaxhighlight> |
|||
</lang> |
|||
{out} |
{out} |
||
<pre> |
<pre> |
||
Line 1,087: | Line 1,087: | ||
=={{header|ERRE}}== |
=={{header|ERRE}}== |
||
<lang> |
<syntaxhighlight lang="text"> |
||
PROGRAM SEMIPRIME_NUMBER |
PROGRAM SEMIPRIME_NUMBER |
||
Line 1,114: | Line 1,114: | ||
PRINT |
PRINT |
||
END PROGRAM |
END PROGRAM |
||
</syntaxhighlight> |
|||
</lang> |
|||
Output is the same of "C" version. |
Output is the same of "C" version. |
||
=={{header|F_Sharp|F#}}== |
=={{header|F_Sharp|F#}}== |
||
< |
<syntaxhighlight lang="fsharp">let isSemiprime (n: int) = |
||
let rec loop currentN candidateFactor numberOfFactors = |
let rec loop currentN candidateFactor numberOfFactors = |
||
if numberOfFactors > 2 then numberOfFactors |
if numberOfFactors > 2 then numberOfFactors |
||
Line 1,132: | Line 1,132: | ||
|> Seq.choose (fun n -> if isSemiprime n then Some(n) else None) |
|> Seq.choose (fun n -> if isSemiprime n then Some(n) else None) |
||
|> Seq.toList |
|> Seq.toList |
||
|> printfn "%A"</ |
|> printfn "%A"</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>[4; 6; 9; 10; 14; 15; 21; 22; 25; 26; 33; 34; 35; 38; 39; 46; 49; 51; 55; 57; 58; 62; 65; 69; 74; 77; 82; 85; 86; 87; 91; 93; 94; 95] |
<pre>[4; 6; 9; 10; 14; 15; 21; 22; 25; 26; 33; 34; 35; 38; 39; 46; 49; 51; 55; 57; 58; 62; 65; 69; 74; 77; 82; 85; 86; 87; 91; 93; 94; 95] |
||
Line 1,140: | Line 1,140: | ||
=={{header|Factor}}== |
=={{header|Factor}}== |
||
{{works with|Factor|0.98}} |
{{works with|Factor|0.98}} |
||
<lang>USING: io kernel math.primes.factors prettyprint sequences ; |
<syntaxhighlight lang="text">USING: io kernel math.primes.factors prettyprint sequences ; |
||
: semiprime? ( n -- ? ) factors length 2 = ;</ |
: semiprime? ( n -- ? ) factors length 2 = ;</syntaxhighlight> |
||
Displaying the semiprimes under 100: |
Displaying the semiprimes under 100: |
||
<lang>100 <iota> [ semiprime? ] filter [ bl ] [ pprint ] interleave nl</ |
<syntaxhighlight lang="text">100 <iota> [ semiprime? ] filter [ bl ] [ pprint ] interleave nl</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,153: | Line 1,153: | ||
=={{header|Forth}}== |
=={{header|Forth}}== |
||
< |
<syntaxhighlight lang="forth">: semiprime? |
||
0 swap dup 2 do |
0 swap dup 2 do |
||
begin dup i mod 0= while i / swap 1+ swap repeat |
begin dup i mod 0= while i / swap 1+ swap repeat |
||
Line 1,160: | Line 1,160: | ||
; |
; |
||
: test 100 2 do i semiprime? if i . then loop cr ;</ |
: test 100 2 do i semiprime? if i . then loop cr ;</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,168: | Line 1,168: | ||
=={{header|Frink}}== |
=={{header|Frink}}== |
||
< |
<syntaxhighlight lang="frink">isSemiprime[n] := |
||
{ |
{ |
||
factors = factor[n] |
factors = factor[n] |
||
Line 1,176: | Line 1,176: | ||
return sum == 2 |
return sum == 2 |
||
}</ |
}</syntaxhighlight> |
||
=={{header|Go}}== |
=={{header|Go}}== |
||
< |
<syntaxhighlight lang="go">package main |
||
import "fmt" |
import "fmt" |
||
Line 1,201: | Line 1,201: | ||
fmt.Println(v, "->", semiprime(v)) |
fmt.Println(v, "->", semiprime(v)) |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,214: | Line 1,214: | ||
=={{header|Haskell}}== |
=={{header|Haskell}}== |
||
{{libheader|Data.Numbers.Primes}} |
{{libheader|Data.Numbers.Primes}} |
||
< |
<syntaxhighlight lang="haskell">isSemiprime :: Int -> Bool |
||
isSemiprime n = (length factors) == 2 && (product factors) == n || |
isSemiprime n = (length factors) == 2 && (product factors) == n || |
||
(length factors) == 1 && (head factors) ^ 2 == n |
(length factors) == 1 && (head factors) ^ 2 == n |
||
where factors = primeFactors n</ |
where factors = primeFactors n</syntaxhighlight> |
||
Alternative (and faster) implementation using pattern matching: |
Alternative (and faster) implementation using pattern matching: |
||
< |
<syntaxhighlight lang="haskell">isSemiprime :: Int -> Bool |
||
isSemiprime n = case (primeFactors n) of |
isSemiprime n = case (primeFactors n) of |
||
[f1, f2] -> f1 * f2 == n |
[f1, f2] -> f1 * f2 == n |
||
otherwise -> False</ |
otherwise -> False</syntaxhighlight> |
||
=={{header|Icon}} and {{header|Unicon}}== |
=={{header|Icon}} and {{header|Unicon}}== |
||
Works in both languages: |
Works in both languages: |
||
< |
<syntaxhighlight lang="unicon">link "factors" |
||
procedure main(A) |
procedure main(A) |
||
Line 1,236: | Line 1,236: | ||
procedure semiprime(n) # Succeeds and produces the factors only if n is semiprime. |
procedure semiprime(n) # Succeeds and produces the factors only if n is semiprime. |
||
return (2 = *(nf := factors(n)), nf) |
return (2 = *(nf := factors(n)), nf) |
||
end</ |
end</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
Line 1,250: | Line 1,250: | ||
Implementation: |
Implementation: |
||
< |
<syntaxhighlight lang="j">isSemiPrime=: 2 = #@q: ::0:"0</syntaxhighlight> |
||
Example use: find all semiprimes less than 100: |
Example use: find all semiprimes less than 100: |
||
< |
<syntaxhighlight lang="j"> I. isSemiPrime i.100 |
||
4 6 9 10 14 15 21 22 25 26 33 34 35 38 39 46 49 51 55 57 58 62 65 69 74 77 82 85 86 87 91 93 94 95</ |
4 6 9 10 14 15 21 22 25 26 33 34 35 38 39 46 49 51 55 57 58 62 65 69 74 77 82 85 86 87 91 93 94 95</syntaxhighlight> |
||
Description: factor the number and count the primes in the factorization, is it 2? |
Description: factor the number and count the primes in the factorization, is it 2? |
||
Line 1,264: | Line 1,264: | ||
Like the Ada example here, this borrows from [[Prime decomposition#Java|Prime decomposition]] and shows the semiprimes below 100 and from 1675 to 1680. |
Like the Ada example here, this borrows from [[Prime decomposition#Java|Prime decomposition]] and shows the semiprimes below 100 and from 1675 to 1680. |
||
< |
<syntaxhighlight lang="java5">import java.math.BigInteger; |
||
import java.util.ArrayList; |
import java.util.ArrayList; |
||
import java.util.List; |
import java.util.List; |
||
Line 1,320: | Line 1,320: | ||
} |
} |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>4 6 9 10 14 15 21 22 25 26 27 33 34 35 38 39 46 49 51 55 57 58 62 65 69 74 77 81 82 85 86 87 91 93 94 95 |
<pre>4 6 9 10 14 15 21 22 25 26 27 33 34 35 38 39 46 49 51 55 57 58 62 65 69 74 77 81 82 85 86 87 91 93 94 95 |
||
Line 1,331: | Line 1,331: | ||
See e.g. [[Erd%C5%91s-primes#jq]] for a suitable implementation of `is_prime`. |
See e.g. [[Erd%C5%91s-primes#jq]] for a suitable implementation of `is_prime`. |
||
<syntaxhighlight lang="jq"> |
|||
<lang jq> |
|||
# Output: a stream of proper factors (probably unsorted) |
# Output: a stream of proper factors (probably unsorted) |
||
def proper_factors: |
def proper_factors: |
||
Line 1,345: | Line 1,345: | ||
| any(proper_factors; |
| any(proper_factors; |
||
is_prime and (($n / .) | (. == $n or is_prime) ); |
is_prime and (($n / .) | (. == $n or is_prime) ); |
||
</syntaxhighlight> |
|||
</lang> |
|||
'''Examples''' |
'''Examples''' |
||
<syntaxhighlight lang="jq"> |
|||
<lang jq> |
|||
(1679, 1680) | "\(.) => \(is_semiprime)" |
(1679, 1680) | "\(.) => \(is_semiprime)" |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,359: | Line 1,359: | ||
{{works with|Julia|0.6}} |
{{works with|Julia|0.6}} |
||
< |
<syntaxhighlight lang="julia">using Primes |
||
issemiprime(n::Integer) = sum(values(factor(n))) == 2 |
issemiprime(n::Integer) = sum(values(factor(n))) == 2 |
||
@show filter(issemiprime, 1:100)</ |
@show filter(issemiprime, 1:100)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,368: | Line 1,368: | ||
=={{header|Kotlin}}== |
=={{header|Kotlin}}== |
||
{{trans|Go}} |
{{trans|Go}} |
||
< |
<syntaxhighlight lang="scala">// version 1.1.2 |
||
fun isSemiPrime(n: Int): Boolean { |
fun isSemiPrime(n: Int): Boolean { |
||
Line 1,385: | Line 1,385: | ||
for (v in 1675..1680) |
for (v in 1675..1680) |
||
println("$v ${if (isSemiPrime(v)) "is" else "isn't"} semi-prime") |
println("$v ${if (isSemiPrime(v)) "is" else "isn't"} semi-prime") |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,398: | Line 1,398: | ||
=={{header|Ksh}}== |
=={{header|Ksh}}== |
||
< |
<syntaxhighlight lang="ksh"> |
||
#!/bin/ksh |
#!/bin/ksh |
||
Line 1,434: | Line 1,434: | ||
done |
done |
||
echo |
echo |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}}<pre> |
{{out}}<pre> |
||
4 6 9 10 14 15 21 22 25 26 33 34 35 38 39 46 49 51 55 57 58 62 65 69 74 77 82 85 86 87 91 93 94 95 |
4 6 9 10 14 15 21 22 25 26 33 34 35 38 39 46 49 51 55 57 58 62 65 69 74 77 82 85 86 87 91 93 94 95 |
||
Line 1,440: | Line 1,440: | ||
=={{header|Lingo}}== |
=={{header|Lingo}}== |
||
< |
<syntaxhighlight lang="lingo">on isSemiPrime (n) |
||
div = 2 |
div = 2 |
||
cnt = 0 |
cnt = 0 |
||
Line 1,452: | Line 1,452: | ||
end repeat |
end repeat |
||
return cnt=2 |
return cnt=2 |
||
end</ |
end</syntaxhighlight> |
||
< |
<syntaxhighlight lang="lingo">res = [] |
||
repeat with i = 1 to 100 |
repeat with i = 1 to 100 |
||
if isSemiPrime(i) then res.add(i) |
if isSemiPrime(i) then res.add(i) |
||
end repeat |
end repeat |
||
put res</ |
put res</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,466: | Line 1,466: | ||
=={{header|Lua}}== |
=={{header|Lua}}== |
||
<syntaxhighlight lang="lua"> |
|||
<lang Lua> |
|||
function semiprime (n) |
function semiprime (n) |
||
local divisor, count = 2, 0 |
local divisor, count = 2, 0 |
||
Line 1,483: | Line 1,483: | ||
print(n, semiprime(n)) |
print(n, semiprime(n)) |
||
end |
end |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,495: | Line 1,495: | ||
=={{header|Maple}}== |
=={{header|Maple}}== |
||
< |
<syntaxhighlight lang="maple">SemiPrimes := proc( n ) |
||
local fact; |
local fact; |
||
fact := NumberTheory:-Divisors( n ) minus {1, n}; |
fact := NumberTheory:-Divisors( n ) minus {1, n}; |
||
Line 1,504: | Line 1,504: | ||
end if; |
end if; |
||
end proc: |
end proc: |
||
{ seq( SemiPrimes( i ), i = 1..100 ) };</ |
{ seq( SemiPrimes( i ), i = 1..100 ) };</syntaxhighlight> |
||
Output: |
Output: |
||
<syntaxhighlight lang="maple"> |
|||
<lang Maple> |
|||
{ 4,6,9,10,14,15,21,22,25,26,33,34,35,38,39,46,49,51,55,57,58,62,65,69,74,77,82,85,86,87,91,93,94,95 } |
{ 4,6,9,10,14,15,21,22,25,26,33,34,35,38,39,46,49,51,55,57,58,62,65,69,74,77,82,85,86,87,91,93,94,95 } |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Mathematica}}/{{header|Wolfram Language}}== |
=={{header|Mathematica}}/{{header|Wolfram Language}}== |
||
< |
<syntaxhighlight lang="mathematica">semiPrimeQ[n_Integer] := Module[{factors, numfactors}, |
||
factors = FactorInteger[n] // Transpose; |
factors = FactorInteger[n] // Transpose; |
||
numfactors = factors[[2]] // Total ; |
numfactors = factors[[2]] // Total ; |
||
numfactors == 2 |
numfactors == 2 |
||
]</ |
]</syntaxhighlight> |
||
Example use: find all semiprimes less than 100: |
Example use: find all semiprimes less than 100: |
||
< |
<syntaxhighlight lang="mathematica">semiPrimeQ[#] & /@ Range[100]; |
||
Position[%, True] // Flatten</ |
Position[%, True] // Flatten</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>{4, 6, 9, 10, 14, 15, 21, 22, 25, 26, 33, 34, 35, 38, 39, 46, 49, 51, |
<pre>{4, 6, 9, 10, 14, 15, 21, 22, 25, 26, 33, 34, 35, 38, 39, 46, 49, 51, |
||
Line 1,524: | Line 1,524: | ||
=={{header|MiniScript}}== |
=={{header|MiniScript}}== |
||
< |
<syntaxhighlight lang="miniscript">isSemiprime = function(num) |
||
divisor = 2 |
divisor = 2 |
||
primes = 0 |
primes = 0 |
||
Line 1,543: | Line 1,543: | ||
if isSemiprime(i) then results.push i |
if isSemiprime(i) then results.push i |
||
end for |
end for |
||
print results</ |
print results</syntaxhighlight> |
||
{{output}} |
{{output}} |
||
Line 1,551: | Line 1,551: | ||
=={{header|NewLisp}}== |
=={{header|NewLisp}}== |
||
<syntaxhighlight lang="newlisp"> |
|||
<lang NewLisp> |
|||
;;; Practically identical to the EchoLisp solution |
;;; Practically identical to the EchoLisp solution |
||
(define (semiprime? n) |
(define (semiprime? n) |
||
Line 1,561: | Line 1,561: | ||
(while (not (semiprime? x)) (-- x)) |
(while (not (semiprime? x)) (-- x)) |
||
(println "Biggest semiprime reachable: " x " = " ((factor x) 0) " x " ((factor x) 1)) |
(println "Biggest semiprime reachable: " x " = " ((factor x) 0) " x " ((factor x) 1)) |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{output}} |
{{output}} |
||
<pre> |
<pre> |
||
Line 1,569: | Line 1,569: | ||
=={{header|Nim}}== |
=={{header|Nim}}== |
||
< |
<syntaxhighlight lang="nim">proc isSemiPrime(k: int): bool = |
||
var |
var |
||
i = 2 |
i = 2 |
||
Line 1,583: | Line 1,583: | ||
for k in 1675..1680: |
for k in 1675..1680: |
||
echo k, (if k.isSemiPrime(): " is" else: " isn’t"), " semi-prime"</ |
echo k, (if k.isSemiPrime(): " is" else: " isn’t"), " semi-prime"</syntaxhighlight> |
||
{{output}} |
{{output}} |
||
Line 1,596: | Line 1,596: | ||
=={{header|Objeck}}== |
=={{header|Objeck}}== |
||
{{trans|Go}} |
{{trans|Go}} |
||
< |
<syntaxhighlight lang="objeck"> |
||
class SemiPrime { |
class SemiPrime { |
||
function : Main(args : String[]) ~ Nil { |
function : Main(args : String[]) ~ Nil { |
||
Line 1,621: | Line 1,621: | ||
return nf = 2; |
return nf = 2; |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
Output: |
Output: |
||
Line 1,628: | Line 1,628: | ||
=={{header|Oforth}}== |
=={{header|Oforth}}== |
||
< |
<syntaxhighlight lang="oforth">func: semiprime(n) |
||
| i | |
| i | |
||
0 2 n sqrt asInteger for: i [ while(n i /mod swap 0 &=) [ ->n 1+ ] drop ] |
0 2 n sqrt asInteger for: i [ while(n i /mod swap 0 &=) [ ->n 1+ ] drop ] |
||
n 1 > ifTrue: [ 1+ ] 2 == ; </ |
n 1 > ifTrue: [ 1+ ] 2 == ; </syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,640: | Line 1,640: | ||
=={{header|PARI/GP}}== |
=={{header|PARI/GP}}== |
||
< |
<syntaxhighlight lang="parigp">issemi(n)=bigomega(n)==2</syntaxhighlight> |
||
A faster version might use trial division and primality testing: |
A faster version might use trial division and primality testing: |
||
< |
<syntaxhighlight lang="parigp">issemi(n)={ |
||
forprime(p=2,97,if(n%p==0, return(isprime(n/p)))); |
forprime(p=2,97,if(n%p==0, return(isprime(n/p)))); |
||
if(isprime(n), return(0)); |
if(isprime(n), return(0)); |
||
bigomega(n)==2 |
bigomega(n)==2 |
||
};</ |
};</syntaxhighlight> |
||
To get faster, partial factorization can be used. At this time GP does not have access to meaningful partial factorization (though it can get it to some extent through flags on <code>factorint</code>), so this version is in PARI: |
To get faster, partial factorization can be used. At this time GP does not have access to meaningful partial factorization (though it can get it to some extent through flags on <code>factorint</code>), so this version is in PARI: |
||
< |
<syntaxhighlight lang="c">long |
||
issemiprime(GEN n) |
issemiprime(GEN n) |
||
{ |
{ |
||
Line 1,726: | Line 1,726: | ||
avma = ltop; |
avma = ltop; |
||
return 0; /* never used */ |
return 0; /* never used */ |
||
}</ |
}</syntaxhighlight> |
||
=={{header|Pascal}}== |
=={{header|Pascal}}== |
||
{{libheader|primTrial}}{{works with|Free Pascal}} |
{{libheader|primTrial}}{{works with|Free Pascal}} |
||
< |
<syntaxhighlight lang="pascal">program SemiPrime; |
||
{$IFDEF FPC} |
{$IFDEF FPC} |
||
{$Mode objfpc}// compiler switch to use result |
{$Mode objfpc}// compiler switch to use result |
||
Line 1,771: | Line 1,771: | ||
inc(i); |
inc(i); |
||
until i> k; |
until i> k; |
||
END.</ |
END.</syntaxhighlight> |
||
;output: |
;output: |
||
<pre> |
<pre> |
||
Line 1,792: | Line 1,792: | ||
{{libheader|ntheory}} |
{{libheader|ntheory}} |
||
With late versions of the ntheory module, we can use <tt>is_semiprime</tt> to get answers for 64-bit numbers in single microseconds. |
With late versions of the ntheory module, we can use <tt>is_semiprime</tt> to get answers for 64-bit numbers in single microseconds. |
||
< |
<syntaxhighlight lang="perl">use ntheory "is_semiprime"; |
||
for ([1..100], [1675..1681], [2,4,99,100,1679,5030,32768,1234567,9876543,900660121]) { |
for ([1..100], [1675..1681], [2,4,99,100,1679,5030,32768,1234567,9876543,900660121]) { |
||
print join(" ",grep { is_semiprime($_) } @$_),"\n"; |
print join(" ",grep { is_semiprime($_) } @$_),"\n"; |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>4 6 9 10 14 15 21 22 25 26 33 34 35 38 39 46 49 51 55 57 58 62 65 69 74 77 82 85 86 87 91 93 94 95 |
<pre>4 6 9 10 14 15 21 22 25 26 33 34 35 38 39 46 49 51 55 57 58 62 65 69 74 77 82 85 86 87 91 93 94 95 |
||
Line 1,802: | Line 1,802: | ||
One can also use <tt>factor</tt> in scalar context, which gives the number of factors (like <tt>bigomega</tt> in Pari/GP and <tt>PrimeOmega</tt> in Mathematica). This skips some optimizations but at these small sizes it doesn't matter. |
One can also use <tt>factor</tt> in scalar context, which gives the number of factors (like <tt>bigomega</tt> in Pari/GP and <tt>PrimeOmega</tt> in Mathematica). This skips some optimizations but at these small sizes it doesn't matter. |
||
< |
<syntaxhighlight lang="perl">use ntheory "factor"; |
||
print join(" ", grep { scalar factor($_) == 2 } 1..100),"\n";</ |
print join(" ", grep { scalar factor($_) == 2 } 1..100),"\n";</syntaxhighlight> |
||
While <tt>is_semiprime</tt> is the fastest way, we can do some of its pre-tests by hand, such as: |
While <tt>is_semiprime</tt> is the fastest way, we can do some of its pre-tests by hand, such as: |
||
< |
<syntaxhighlight lang="perl">use ntheory qw/factor is_prime trial_factor/; |
||
sub issemi { |
sub issemi { |
||
my $n = shift; |
my $n = shift; |
||
Line 1,814: | Line 1,814: | ||
} |
} |
||
2 == factor($n); |
2 == factor($n); |
||
}</ |
}</syntaxhighlight> |
||
=={{header|Phix}}== |
=={{header|Phix}}== |
||
<!--< |
<!--<syntaxhighlight lang="phix">--> |
||
<span style="color: #008080;">function</span> <span style="color: #000000;">semiprime</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span> |
<span style="color: #008080;">function</span> <span style="color: #000000;">semiprime</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span> |
||
<span style="color: #008080;">return</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">prime_factors</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #004600;">true</span><span style="color: #0000FF;">))==</span><span style="color: #000000;">2</span> |
<span style="color: #008080;">return</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">prime_factors</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #004600;">true</span><span style="color: #0000FF;">))==</span><span style="color: #000000;">2</span> |
||
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
||
<span style="color: #7060A8;">pp</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">filter</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">tagset</span><span style="color: #0000FF;">(</span><span style="color: #000000;">100</span><span style="color: #0000FF;">)&</span><span style="color: #7060A8;">tagset</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1680</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1675</span><span style="color: #0000FF;">),</span><span style="color: #000000;">semiprime</span><span style="color: #0000FF;">),{</span><span style="color: #004600;">pp_IntCh</span><span style="color: #0000FF;">,</span><span style="color: #004600;">false</span><span style="color: #0000FF;">})</span> |
<span style="color: #7060A8;">pp</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">filter</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">tagset</span><span style="color: #0000FF;">(</span><span style="color: #000000;">100</span><span style="color: #0000FF;">)&</span><span style="color: #7060A8;">tagset</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1680</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1675</span><span style="color: #0000FF;">),</span><span style="color: #000000;">semiprime</span><span style="color: #0000FF;">),{</span><span style="color: #004600;">pp_IntCh</span><span style="color: #0000FF;">,</span><span style="color: #004600;">false</span><span style="color: #0000FF;">})</span> |
||
<!--</ |
<!--</syntaxhighlight>--> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,831: | Line 1,831: | ||
=={{header|PHP}}== |
=={{header|PHP}}== |
||
{{trans|TypeScript}} |
{{trans|TypeScript}} |
||
< |
<syntaxhighlight lang="php"> |
||
<?php |
<?php |
||
// Semiprime |
// Semiprime |
||
Line 1,853: | Line 1,853: | ||
"It is a semiprime.\n" : "It is not a semiprime.\n"); |
"It is a semiprime.\n" : "It is not a semiprime.\n"); |
||
?> |
?> |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,865: | Line 1,865: | ||
=={{header|PicoLisp}}== |
=={{header|PicoLisp}}== |
||
< |
<syntaxhighlight lang="picolisp">(de factor (N) |
||
(make |
(make |
||
(let |
(let |
||
Line 1,885: | Line 1,885: | ||
(conc (range 1 100) (range 1675 1680)) ) ) |
(conc (range 1 100) (range 1675 1680)) ) ) |
||
(bye)</ |
(bye)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>(4 6 9 10 14 15 21 22 25 26 33 34 35 38 39 46 49 51 55 57 58 62 65 69 74 77 82 85 86 87 91 93 94 95 1678 1679)</pre> |
<pre>(4 6 9 10 14 15 21 22 25 26 33 34 35 38 39 46 49 51 55 57 58 62 65 69 74 77 82 85 86 87 91 93 94 95 1678 1679)</pre> |
||
=={{header|PL/I}}== |
=={{header|PL/I}}== |
||
< |
<syntaxhighlight lang="pli">*process source attributes xref nest or(!); |
||
/*-------------------------------------------------------------------- |
/*-------------------------------------------------------------------- |
||
* 22.02.2014 Walter Pachl using the is_prime code from |
* 22.02.2014 Walter Pachl using the is_prime code from |
||
Line 1,979: | Line 1,979: | ||
End spb; |
End spb; |
||
</syntaxhighlight> |
|||
</lang> |
|||
'''Output:''' |
'''Output:''' |
||
<pre> 900660121 1 is semiprime 30011*30011 |
<pre> 900660121 1 is semiprime 30011*30011 |
||
Line 1,993: | Line 1,993: | ||
=={{header|PowerShell}}== |
=={{header|PowerShell}}== |
||
<syntaxhighlight lang="powershell"> |
|||
<lang PowerShell> |
|||
function isPrime ($n) { |
function isPrime ($n) { |
||
if ($n -le 1) {$false} |
if ($n -le 1) {$false} |
||
Line 2,020: | Line 2,020: | ||
$OFS = " " |
$OFS = " " |
||
"semiprime form 1 to 100: $(1..100 | where {semiprime $_})" |
"semiprime form 1 to 100: $(1..100 | where {semiprime $_})" |
||
</syntaxhighlight> |
|||
</lang> |
|||
<b>Output:</b> |
<b>Output:</b> |
||
<pre> |
<pre> |
||
Line 2,033: | Line 2,033: | ||
=={{header|Python}}== |
=={{header|Python}}== |
||
This imports [[Prime decomposition#Python]] |
This imports [[Prime decomposition#Python]] |
||
< |
<syntaxhighlight lang="python">from prime_decomposition import decompose |
||
def semiprime(n): |
def semiprime(n): |
||
Line 2,040: | Line 2,040: | ||
return next(d) * next(d) == n |
return next(d) * next(d) == n |
||
except StopIteration: |
except StopIteration: |
||
return False</ |
return False</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
From Idle: |
From Idle: |
||
< |
<syntaxhighlight lang="python">>>> semiprime(1679) |
||
True |
True |
||
>>> [n for n in range(1,101) if semiprime(n)] |
>>> [n for n in range(1,101) if semiprime(n)] |
||
[4, 6, 9, 10, 14, 15, 21, 22, 25, 26, 33, 34, 35, 38, 39, 46, 49, 51, 55, 57, 58, 62, 65, 69, 74, 77, 82, 85, 86, 87, 91, 93, 94, 95] |
[4, 6, 9, 10, 14, 15, 21, 22, 25, 26, 33, 34, 35, 38, 39, 46, 49, 51, 55, 57, 58, 62, 65, 69, 74, 77, 82, 85, 86, 87, 91, 93, 94, 95] |
||
>>> </ |
>>> </syntaxhighlight> |
||
=={{header|Quackery}}== |
=={{header|Quackery}}== |
||
Line 2,054: | Line 2,054: | ||
<code>factors</code> is defined at [http://rosettacode.org/wiki/Factors_of_an_integer#Quackery Factors of an integer]. |
<code>factors</code> is defined at [http://rosettacode.org/wiki/Factors_of_an_integer#Quackery Factors of an integer]. |
||
< |
<syntaxhighlight lang="quackery"> [ factors size dup 3 4 clamp = ] is semiprime ( n --> b ) |
||
say "Semiprimes less than 100:" cr |
say "Semiprimes less than 100:" cr |
||
100 times [ i^ semiprime if [ i^ echo sp ] ]</ |
100 times [ i^ semiprime if [ i^ echo sp ] ]</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 2,066: | Line 2,066: | ||
=={{header|Racket}}== |
=={{header|Racket}}== |
||
The first implementation considers all pairs of factors multiplying up to the given number and determines if any of them is a pair of primes. |
The first implementation considers all pairs of factors multiplying up to the given number and determines if any of them is a pair of primes. |
||
< |
<syntaxhighlight lang="racket">#lang racket |
||
(require math) |
(require math) |
||
Line 2,080: | Line 2,080: | ||
(for/or ((pair (pair-factorize n))) |
(for/or ((pair (pair-factorize n))) |
||
(for/and ((el pair)) |
(for/and ((el pair)) |
||
(prime? el))))</ |
(prime? el))))</syntaxhighlight> |
||
The alternative implementation operates directly on the list of prime factors and their multiplicities. It is approximately 1.6 times faster than the first one (according to some simple tests of mine). |
The alternative implementation operates directly on the list of prime factors and their multiplicities. It is approximately 1.6 times faster than the first one (according to some simple tests of mine). |
||
< |
<syntaxhighlight lang="racket">#lang racket |
||
(require math) |
(require math) |
||
Line 2,094: | Line 2,094: | ||
(= (expt (caar prime-factors) (cadar prime-factors)) n)) |
(= (expt (caar prime-factors) (cadar prime-factors)) n)) |
||
(and (= (length prime-factors) 2) |
(and (= (length prime-factors) 2) |
||
(= (foldl (λ (x y) (* (car x) y)) 1 prime-factors) n)))))</ |
(= (foldl (λ (x y) (* (car x) y)) 1 prime-factors) n)))))</syntaxhighlight> |
||
=={{header|Raku}}== |
=={{header|Raku}}== |
||
(formerly Perl 6) |
(formerly Perl 6) |
||
Here is a naive, grossly inefficient implementation. |
Here is a naive, grossly inefficient implementation. |
||
<lang |
<syntaxhighlight lang="raku" line>sub is-semiprime (Int $n --> Bool) { |
||
not $n.is-prime and |
not $n.is-prime and |
||
.is-prime given |
.is-prime given |
||
Line 2,112: | Line 2,112: | ||
nok is-semiprime([*] my @f3 = @primes.roll(3)), ~@f3; |
nok is-semiprime([*] my @f3 = @primes.roll(3)), ~@f3; |
||
nok is-semiprime([*] my @f4 = @primes.roll(4)), ~@f4; |
nok is-semiprime([*] my @f4 = @primes.roll(4)), ~@f4; |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>ok 1 - 17 |
<pre>ok 1 - 17 |
||
Line 2,139: | Line 2,139: | ||
{{works with|Rakudo|2017.02}} |
{{works with|Rakudo|2017.02}} |
||
<lang |
<syntaxhighlight lang="raku" line>sub is-semiprime ( Int $n where * > 0 ) { |
||
return False if $n.is-prime; |
return False if $n.is-prime; |
||
my $factor = find-factor( $n ); |
my $factor = find-factor( $n ); |
||
Line 2,177: | Line 2,177: | ||
say 'elapsed seconds: ', now - $start; |
say 'elapsed seconds: ', now - $start; |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre>Semiprimes less than 100: |
<pre>Semiprimes less than 100: |
||
Line 2,217: | Line 2,217: | ||
=={{header|REXX}}== |
=={{header|REXX}}== |
||
===version 1=== |
===version 1=== |
||
< |
<syntaxhighlight lang="rexx">/* REXX --------------------------------------------------------------- |
||
* 20.02.2014 Walter Pachl relying on 'prime decomposition' |
* 20.02.2014 Walter Pachl relying on 'prime decomposition' |
||
* 21.02.2014 WP Clarification: I copied the algorithm created by |
* 21.02.2014 WP Clarification: I copied the algorithm created by |
||
Line 2,272: | Line 2,272: | ||
z=z%j /*% (percent) is integer divide.*/ |
z=z%j /*% (percent) is integer divide.*/ |
||
end /*while z··· */ /* // ?---remainder integer ÷.*/ |
end /*while z··· */ /* // ?---remainder integer ÷.*/ |
||
return /*finished, now return to invoker*/</ |
return /*finished, now return to invoker*/</syntaxhighlight> |
||
'''Output''' |
'''Output''' |
||
<pre>4 is semiprime 2 2 |
<pre>4 is semiprime 2 2 |
||
Line 2,286: | Line 2,286: | ||
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. |
||
< |
<syntaxhighlight 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*/ |
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.*/ |
||
Line 2,320: | Line 2,320: | ||
else return 0 |
else return 0 |
||
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.*/</ |
end /*j*/ /* [↑] J is never a multiple of three.*/</syntaxhighlight> |
||
{{out|output|text= when using the input of: <tt> -1 106 </tt>}} |
{{out|output|text= when using the input of: <tt> -1 106 </tt>}} |
||
Line 2,496: | Line 2,496: | ||
It gets its speed increase by the use of memoization of the prime numbers found, an unrolled primality (division) check, and other speed improvements. |
It gets its speed increase by the use of memoization of the prime numbers found, an unrolled primality (division) check, and other speed improvements. |
||
< |
<syntaxhighlight 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*/ |
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.*/ |
||
Line 2,536: | Line 2,536: | ||
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.*/ |
end /*j*/ /* [↑] J is never a multiple of three.*/ |
||
return 0</ |
return 0</syntaxhighlight> |
||
{{out|output|text= is identical to the previous REXX version.}} <br><br> |
{{out|output|text= is identical to the previous REXX version.}} <br><br> |
||
=={{header|Ring}}== |
=={{header|Ring}}== |
||
< |
<syntaxhighlight lang="ring"> |
||
prime = 1679 |
prime = 1679 |
||
decomp(prime) |
decomp(prime) |
||
Line 2,565: | Line 2,565: | ||
next |
next |
||
return true |
return true |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Ruby}}== |
=={{header|Ruby}}== |
||
< |
<syntaxhighlight lang="ruby">require 'prime' |
||
# 75.prime_division # Returns the factorization.75 divides by 3 once and by 5 twice => [[3, 1], [5, 2]] |
# 75.prime_division # Returns the factorization.75 divides by 3 once and by 5 twice => [[3, 1], [5, 2]] |
||
Line 2,580: | Line 2,580: | ||
p ( 1..100 ).select( &:semi_prime? ) |
p ( 1..100 ).select( &:semi_prime? ) |
||
# [4, 6, 9, 10, 14, 15, 21, 22, 25, 26, 33, 34, 35, 38, 39, 46, 49, 51, 55, 57, 58, 62, 65, 69, 74, 77, 82, 85, 86, 87, 91, 93, 94, 95] |
# [4, 6, 9, 10, 14, 15, 21, 22, 25, 26, 33, 34, 35, 38, 39, 46, 49, 51, 55, 57, 58, 62, 65, 69, 74, 77, 82, 85, 86, 87, 91, 93, 94, 95] |
||
</syntaxhighlight> |
|||
</lang> |
|||
Faster version using 'factor' function from [U|Li]nux Core Utilities library. |
Faster version using 'factor' function from [U|Li]nux Core Utilities library. |
||
< |
<syntaxhighlight lang="ruby">def semiprime(n) |
||
`factor #{n}`.split(' ').size == 3 |
`factor #{n}`.split(' ').size == 3 |
||
end |
end |
||
n = 2**72 - 1 #4722366482869645213695 |
n = 2**72 - 1 #4722366482869645213695 |
||
(n-50..n).each { |n| puts "#{n} -> #{semiprime(n)}" }</ |
(n-50..n).each { |n| puts "#{n} -> #{semiprime(n)}" }</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>4722366482869645213645 -> false |
<pre>4722366482869645213645 -> false |
||
Line 2,642: | Line 2,642: | ||
=={{header|Rust}}== |
=={{header|Rust}}== |
||
<lang>extern crate primal; |
<syntaxhighlight lang="text">extern crate primal; |
||
fn isqrt(n: usize) -> usize { |
fn isqrt(n: usize) -> usize { |
||
Line 2,697: | Line 2,697: | ||
fn test6() { |
fn test6() { |
||
assert_eq!((2..1_000_000).filter(|&n| is_semiprime(n)).count(), 210_035); |
assert_eq!((2..1_000_000).filter(|&n| is_semiprime(n)).count(), 210_035); |
||
}</ |
}</syntaxhighlight> |
||
functional version of is_semiprime: |
functional version of is_semiprime: |
||
< |
<syntaxhighlight lang="rust">fn is_semiprime(n: usize) -> bool { |
||
fn iter(x: usize, start: usize, acc: &[usize]) -> Vec<usize> { |
fn iter(x: usize, start: usize, acc: &[usize]) -> Vec<usize> { |
||
if acc.len() > 2 {return acc.to_vec()} // break for semi_prime |
if acc.len() > 2 {return acc.to_vec()} // break for semi_prime |
||
Line 2,710: | Line 2,710: | ||
} |
} |
||
iter(n, 2, &[]).len() == 2 |
iter(n, 2, &[]).len() == 2 |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 2,726: | Line 2,726: | ||
=={{header|Scala}}== |
=={{header|Scala}}== |
||
{{works with|Scala 2.9.1}} |
{{works with|Scala 2.9.1}} |
||
< |
<syntaxhighlight lang="scala">object Semiprime extends App { |
||
def isSP(n: Int): Boolean = { |
def isSP(n: Int): Boolean = { |
||
Line 2,745: | Line 2,745: | ||
1675 to 1681 foreach {i => println(i+" -> "+isSP(i))} |
1675 to 1681 foreach {i => println(i+" -> "+isSP(i))} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>4 6 9 10 14 15 21 22 25 26 33 34 35 38 39 46 49 51 55 57 58 62 65 69 74 77 82 85 86 87 91 93 94 95 |
<pre>4 6 9 10 14 15 21 22 25 26 33 34 35 38 39 46 49 51 55 57 58 62 65 69 74 77 82 85 86 87 91 93 94 95 |
||
Line 2,757: | Line 2,757: | ||
=={{header|Seed7}}== |
=={{header|Seed7}}== |
||
< |
<syntaxhighlight lang="seed7">$ include "seed7_05.s7i"; |
||
const func boolean: semiPrime (in var integer: n) is func |
const func boolean: semiPrime (in var integer: n) is func |
||
Line 2,783: | Line 2,783: | ||
writeln(v <& " -> " <& semiPrime(v)); |
writeln(v <& " -> " <& semiPrime(v)); |
||
end for; |
end for; |
||
end func;</ |
end func;</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 2,797: | Line 2,797: | ||
=={{header|Sidef}}== |
=={{header|Sidef}}== |
||
Built-in: |
Built-in: |
||
< |
<syntaxhighlight lang="ruby">say is_semiprime(2**128 + 1) #=> true |
||
say is_semiprime(2**256 - 1) #=> false</ |
say is_semiprime(2**256 - 1) #=> false</syntaxhighlight> |
||
User-defined function, with trial division up to a given bound '''B''': |
User-defined function, with trial division up to a given bound '''B''': |
||
< |
<syntaxhighlight lang="ruby">func is_semiprime(n, B=1e4) { |
||
with (n.trial_factor(B)) { |f| |
with (n.trial_factor(B)) { |f| |
||
Line 2,811: | Line 2,811: | ||
} |
} |
||
say [2,4,99,100,1679,32768,1234567,9876543,900660121].grep(is_semiprime)</ |
say [2,4,99,100,1679,32768,1234567,9876543,900660121].grep(is_semiprime)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 2,819: | Line 2,819: | ||
=={{header|Swift}}== |
=={{header|Swift}}== |
||
< |
<syntaxhighlight lang="swift">import Foundation |
||
func primes(n: Int) -> AnyGenerator<Int> { |
func primes(n: Int) -> AnyGenerator<Int> { |
||
Line 2,855: | Line 2,855: | ||
} |
} |
||
return false |
return false |
||
}</ |
}</syntaxhighlight> |
||
=={{header|Tcl}}== |
=={{header|Tcl}}== |
||
{{tcllib|math::numtheory}} |
{{tcllib|math::numtheory}} |
||
< |
<syntaxhighlight lang="tcl">package require math::numtheory |
||
proc isSemiprime n { |
proc isSemiprime n { |
||
Line 2,882: | Line 2,882: | ||
puts "NOT a semiprime" |
puts "NOT a semiprime" |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 2,895: | Line 2,895: | ||
== {{header|TypeScript}} == |
== {{header|TypeScript}} == |
||
{{trans|ASIC}} |
{{trans|ASIC}} |
||
< |
<syntaxhighlight lang="javascript"> |
||
// Semiprime |
// Semiprime |
||
Line 2,920: | Line 2,920: | ||
readline.close(); |
readline.close(); |
||
}); |
}); |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 2,933: | Line 2,933: | ||
=={{header|Wren}}== |
=={{header|Wren}}== |
||
{{trans|Go}} |
{{trans|Go}} |
||
< |
<syntaxhighlight lang="ecmascript">var semiprime = Fn.new { |n| |
||
if (n < 3) return false |
if (n < 3) return false |
||
var nf = 0 |
var nf = 0 |
||
Line 2,948: | Line 2,948: | ||
for (v in 1675..1680) { |
for (v in 1675..1680) { |
||
System.print("%(v) -> %(semiprime.call(v) ? "is" : "is not") semi-prime") |
System.print("%(v) -> %(semiprime.call(v) ? "is" : "is not") semi-prime") |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 2,961: | Line 2,961: | ||
=={{header|XPL0}}== |
=={{header|XPL0}}== |
||
< |
<syntaxhighlight lang="xpl0">func Semiprime(N); \Return 'true' if N is semiprime |
||
int N, F, C; |
int N, F, C; |
||
[C:= 0; F:= 2; |
[C:= 0; F:= 2; |
||
Line 2,977: | Line 2,977: | ||
if Semiprime(N) then |
if Semiprime(N) then |
||
[IntOut(0, N); ChOut(0, ^ )]; |
[IntOut(0, N); ChOut(0, ^ )]; |
||
]</ |
]</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 2,986: | Line 2,986: | ||
=={{header|zkl}}== |
=={{header|zkl}}== |
||
{{trans|C}} |
{{trans|C}} |
||
< |
<syntaxhighlight lang="zkl">fcn semiprime(n){ |
||
reg f = 0; |
reg f = 0; |
||
p:=2; while(f < 2 and p*p <= n){ |
p:=2; while(f < 2 and p*p <= n){ |
||
Line 2,993: | Line 2,993: | ||
} |
} |
||
return(f + (n > 1) == 2); |
return(f + (n > 1) == 2); |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |