Semiprime: Difference between revisions
m
→{{header|EasyLang}}
Drkameleon (talk | contribs) (Added Arturo implementation) |
|||
| (32 intermediate revisions by 18 users not shown) | |||
Line 32:
{{trans|C++}}
<
V a = 2
V b = 0
Line 43:
R b == 2
print((1..100).filter(n -> is_semiprime(n)))</
{{out}}
Line 52:
=={{header|360 Assembly}}==
{{trans|C}}
<
SEMIPRIM CSECT
USING SEMIPRIM,R13 base register
Line 122:
XDEC DS CL12 temp
YREGS
END SEMIPRIM</
{{out}}
<pre>
Line 132:
=={{header|Action!}}==
<
INT a,b
Line 159:
FI
OD
RETURN</
{{out}}
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Semiprime.png Screenshot from Atari 8-bit computer]
Line 175:
This imports the package '''Prime_Numbers''' from [[Prime decomposition#Ada]].
<
procedure Test_Semiprime is
Line 195:
end if;
end loop;
end Test_Semiprime;</
It outputs all semiprimes below 100 and all semiprimes between 1675 and 1680:
Line 212:
=={{header|ALGOL 68}}==
<
# n is semi prime if it has exactly two prime factors #
PROC is semiprime = ( INT n )BOOL:
Line 250:
OD;
print( ( newline ) )
</syntaxhighlight>
{{out}}
<pre>
semi primes below 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
semi primes below between 1670 and 1690: 1671 1673 1678 1679 1681 1685 1687 1689
</pre>
=={{header|ALGOL W}}==
{{Trans|C++}}
<syntaxhighlight lang="algolw">
begin % find some semi-primes - numbers with exactly 2 prime factors %
logical procedure isSemiPrime( integer value v ) ;
begin
integer a, b, c;
a := 2; b := 0; c := v;
while b < 3 and c > 1 do begin
if c rem a = 0 then begin
c := c div a;
b := b + 1
end
else a := a + 1;
end while_b_lt_3_and_c_ne_1 ;
b = 2
end isSemiPrime ;
for x := 2 until 99 do begin
if isSemiPrime( x ) then writeon( i_w := 1, s_w := 0, x, " " )
end for_x
end.
</syntaxhighlight>
{{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>
=={{header|Arturo}}==
<
2 = size factors.prime x
]
print select 1..100 => semiPrime?</
{{out}}
Line 271 ⟶ 299:
=={{header|AutoHotkey}}==
{{works with|AutoHotkey_L}}
<
k := 1
loop, 100
Line 325 ⟶ 353:
}
;=================================================================================================================================================
esc::Exitapp</
{{output}}
<Pre>
Line 336 ⟶ 364:
=={{header|AWK}}==
<syntaxhighlight lang="awk">
# syntax: GAWK -f SEMIPRIME.AWK
BEGIN {
Line 365 ⟶ 393:
return(nf == 2)
}
</syntaxhighlight>
{{out}}
<pre>
Line 376 ⟶ 404:
==={{header|ASIC}}===
{{trans|Tiny BASIC}}
<
REM Semiprime
PRINT "Enter an integer ";
Line 400 ⟶ 428:
ENDIF
END
</syntaxhighlight>
{{out}}
<pre>
Line 412 ⟶ 440:
==={{header|BASIC256}}===
<
a = 2
c = 0
Line 430 ⟶ 458:
print i, semiprime$(i)
next i
end</
==={{header|Chipmunk Basic}}===
{{works with|Chipmunk Basic|3.6.4}}
{{trans|BASIC256}}
<syntaxhighlight lang="qbasic">100 rem Semiprime
110 cls
120 for i = 0 to 64
130 print using "## ";i semiprime$(i)
140 next i
150 end
160 sub semiprime$(n)
170 a = 2
180 c = 0
190 do while c < 3 and n > 1
200 if n mod a = 0 then n = n/a : c = c+1 else a = a+1
210 loop
220 if c = 2 then semiprime$ = "True" else semiprime$ = "False"
230 end sub</syntaxhighlight>
==={{header|FreeBASIC}}===
<
dim as uinteger a = 2, c = 0
while c < 3 andalso n > 1
Line 449 ⟶ 495:
for i as uinteger = 0 to 64
print i, semiprime(i)
next i</
==={{header|GW-BASIC}}===
<
20 N=ABS(N)
30 C = 0
Line 459 ⟶ 505:
60 IF N MOD F = 0 THEN C = C + 1 : N = N / F ELSE F = F + 1
70 IF N > 1 THEN GOTO 60
80 IF C=2 THEN PRINT "It's a semiprime." ELSE PRINT "It is not a semiprime."</
==={{header|Minimal BASIC}}===
Line 465 ⟶ 511:
{{works with|Commodore BASIC|3.5}}
{{works with|Nascom ROM BASIC|4.7}}
<
10 REM Semiprime
20 PRINT "Enter an integer";
Line 483 ⟶ 529:
160 PRINT "It is not a semiprime."
170 END
</syntaxhighlight>
==={{header|Palo Alto Tiny BASIC}}===
{{trans|Tiny BASIC}}
<syntaxhighlight lang="basic">
10 REM SEMIPRIME
20 INPUT "ENTER AN INTEGER"N
30 LET N=ABS(N)
40 LET C=0
50 IF N<2 GOTO 90
60 FOR F=2 TO N
70 IF (N/F)*F=N LET C=C+1,N=N/F;GOTO 70
80 NEXT F
90 IF C=2 PRINT "IT IS A SEMIPRIME.";STOP
100 PRINT "IT IS NOT A SEMIPRIME.";STOP
</syntaxhighlight>
{{out}} 2 runs.
<pre>
ENTER AN INTEGER:60
IT IS NOT A SEMIPRIME.
</pre>
<pre>
ENTER AN INTEGER:33
IT IS A SEMIPRIME.
</pre>
==={{header|PureBasic}}===
<
a.i = 2
c.i = 0
Line 510 ⟶ 580:
PrintN(#CRLF$ + "--- terminado, pulsa RETURN---"): Input()
CloseConsole()
End</
==={{header|Run BASIC}}===
<syntaxhighlight lang="vbnet">function semiprime$(n)
a = 2
c = 0
while c < 3 and n > 1
if n mod a = 0 then
n = n / a
c = c + 1
else
a = a + 1
end if
wend
if c = 2 then semiprime$ = "True" else semiprime$ = "False"
end function
for i = 0 to 64
print i; chr$(9); semiprime$(i)
next i</syntaxhighlight>
==={{header|Tiny BASIC}}===
{{works with|TinyBasic}}
<syntaxhighlight lang="basic">10 REM Semiprime
20 PRINT "Enter an integer"
30 INPUT N
40 IF N < 0 THEN LET
50 IF N <
60 LET C = 0
80 IF (N /
90 LET F =
110 GOTO 80
120 IF C = 2 THEN PRINT "It is a semiprime."
130 IF C <> 2 THEN PRINT "It is not a semiprime."
140 END
150 LET C = C + 1
160 LET N = N / F
170 GOTO 80</syntaxhighlight>
{{out}}2 runs.
<pre>
Enter an integer
? 60
It is not a semiprime.
</pre>
<pre>
Enter an integer
? 33
It is a semiprime.
</pre>
==={{header|True BASIC}}===
<syntaxhighlight lang="qbasic">FUNCTION semiprime$ (n)
LET a = 2
LET c = 0
DO WHILE c < 3 AND n > 1
IF REMAINDER(n, a) = 0 THEN
LET n = n / a
LET c = c + 1
ELSE
LET a = a + 1
END IF
LOOP
IF c = 2 THEN LET semiprime$ = "True" ELSE LET semiprime$ = "False"
END FUNCTION
FOR i = 0 TO 64
PRINT i, semiprime$(i)
NEXT i
END</syntaxhighlight>
==={{header|Yabasic}}===
<
a = 2
c = 0
Line 549 ⟶ 671:
print i, chr$(9), semiprime$(i)
next i
end</
=={{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).
<
m n a b
. 2^-64:?m
Line 559 ⟶ 681:
& !arg^!m
: (#%?a^!m*#%?b^!m|#%?a^!n&!a:?b)
& (!a.!b);</
Test with numbers < 2^63:
<
& whl
' ( -1+!u:>2:?u
Line 568 ⟶ 690:
|
)
);</
Output:
Line 619 ⟶ 741:
=={{header|C}}==
<
int semiprime(int n)
Line 639 ⟶ 761:
return 0;
}</
{{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>
=={{header|C sharp|C#}}==
<syntaxhighlight lang="csharp">
static void Main(string[] args)
{
Line 673 ⟶ 795:
return b == 2;
}
</syntaxhighlight>
{{out}}
<pre>
Line 729 ⟶ 851:
=={{header|C++}}==
<
#include <iostream>
Line 751 ⟶ 873:
return 0;
}
</syntaxhighlight>
{{out}}
<pre>
Line 759 ⟶ 881:
=={{header|Clojure}}==
{{trans|C}}
<
(ns example
(:gen-class))
Line 774 ⟶ 896:
(println (filter semi-prime? (range 1 100)))
</syntaxhighlight>
{{Out}}
<pre>
Line 781 ⟶ 903:
=={{header|Common Lisp}}==
<
(cond ((> a (isqrt n)) nil)
((zerop (rem n a)) (and (primep a) (primep (/ n a))))
Line 789 ⟶ 911:
(cond ((> a (isqrt n)) t)
((zerop (rem n a)) nil)
(t (primep n (+ a 1)))))</
Example Usage:
Line 800 ⟶ 922:
=={{header|Crystal}}==
{{trans|D}}
<
nf = 0
(2..n).each do |i|
Line 812 ⟶ 934:
end
(1675..1681).each { |n| puts "#{n} -> #{semiprime(n)}" }</
{{out}}
<pre>1675 -> false
Line 823 ⟶ 945:
Faster version using 'factor' function from [U|Li]nux Core Utilities library.
<
`factor #{n}`.split(' ').size == 3
end
n = 0xffffffffffffffff_u64 # 2**64 - 1 = 18446744073709551615
(n-50..n).each { |n| puts "#{n} -> #{semiprime(n)}" }</
{{out}}
<pre>18446744073709551565 -> false
Line 883 ⟶ 1,005:
=={{header|D}}==
{{trans|Go}}
<
auto nf = 0;
foreach (immutable i; 2 .. n + 1) {
Line 901 ⟶ 1,023:
foreach (immutable n; 1675 .. 1681)
writeln(n, " -> ", n.semiprime);
}</
{{out}}
<pre>1675 -> false
Line 912 ⟶ 1,034:
=={{header|DCL}}==
Given a file primes.txt is the list of primes up to the sqrt(2^31-1), i.e. 46337;
<
$ if p1 .lt. 2
$ then
Line 959 ⟶ 1,081:
$
$ clean:
$ close primes</
{{out}}
<pre>$ @factor 6
Line 969 ⟶ 1,091:
$ @factor 2147483646
FACTORIZATION = "2*3*3*7*11*31*151*331"</pre>
=={{header|Delphi}}==
{{works with|Delphi|6.0}}
{{libheader|SysUtils,StdCtrls}}
<syntaxhighlight lang="Delphi">
{This function would normally be in a library, but it shown here for clarity}
procedure GetAllFactors(N: Integer;var IA: TIntegerDynArray);
{Make a list of all irreducible factor of N}
var I: integer;
begin
SetLength(IA,1);
IA[0]:=1;
for I:=2 to N do
while (N mod I)=0 do
begin
SetLength(IA,Length(IA)+1);
IA[High(IA)]:=I;
N:=N div I;
end;
end;
function IsSemiprime(N: integer): boolean;
{Test if number is semiprime}
var IA: TIntegerDynArray;
begin
{Get all factors of N}
GetAllFactors(N,IA);
Result:=False;
{Since 1 is factor, ignore it}
if Length(IA)<>3 then exit;
Result:=IsPrime(IA[1]) and IsPrime(IA[2]);
end;
procedure Semiprimes(Memo: TMemo);
var I,Cnt: integer;
var S: string;
begin
Cnt:=0;
S:='';
{Test first 100 number to see if they are semiprime}
for I:=0 to 100-1 do
if IsSemiprime(I) then
begin
Inc(Cnt);
S:=S+Format('%4d',[I]);
if (Cnt mod 10)= 0 then S:=S+CRLF;
end;
Memo.Lines.Add(S);
Memo.Lines.Add('Count='+IntToStr(Cnt));
end;
</syntaxhighlight>
{{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
Count=34
Elapsed Time: 5.182 ms.
</pre>
=={{header|EasyLang}}==
<syntaxhighlight>
fastfunc factor num .
i = 2
while i <= sqrt num
if num mod i = 0
return i
.
i += 1
.
return 1
.
func semiprime n .
f1 = factor n
if f1 = 1
return 0
.
f2 = n div f1
if factor f1 = 1 and factor f2 = 1
return 1
.
return 0
.
for i = 1 to 1000
if semiprime i = 1
write i & " "
.
.
</syntaxhighlight>
=={{header|EchoLisp}}==
<
(lib 'math)
(define (semi-prime? n)
Line 992 ⟶ 1,212:
(prime-factors 100000000042)
→ (2 50000000021)
</syntaxhighlight>
=={{header|Elixir}}==
<
def semiprime?(n), do: length(decomposition(n)) == 2
Line 1,008 ⟶ 1,228:
Enum.each(1675..1680, fn n ->
:io.format "~w -> ~w\t~s~n", [n, Prime.semiprime?(n), Prime.decomposition(n)|>Enum.join(" x ")]
end)</
{{out}}
Line 1,025 ⟶ 1,245:
Another using prime factors from [[Prime_decomposition#Erlang]] :
<
-module(factors).
-export([factors/1,kthfactor/2]).
Line 1,045 ⟶ 1,265:
_ ->
false end.
</syntaxhighlight>
{out}
<pre>
Line 1,087 ⟶ 1,307:
=={{header|ERRE}}==
<syntaxhighlight lang="text">
PROGRAM SEMIPRIME_NUMBER
Line 1,114 ⟶ 1,334:
PRINT
END PROGRAM
</syntaxhighlight>
Output is the same of "C" version.
=={{header|Euler}}==
{{Trans|C++}}
<!-- syntaxhighlight lang="euler"> -->
'''begin''' '''new''' isSemiPrime; '''new''' x; '''label''' xLoop;
isSemiPrime <-
` '''formal''' v;
'''begin''' '''new''' a; '''new''' b; '''new''' c; '''label''' again;
a <- 2; b <- 0; c <- v;
again: '''if''' b < 3 '''and''' c > 1 '''then''' '''begin'''
'''if''' c '''mod''' a = 0 '''then''' '''begin'''
c <- c % a;
b <- b + 1
'''end'''
'''else''' a <- a + 1;
'''goto''' again
'''end''' '''else''' 0;
b = 2
'''end'''
'
;
x <- 1;
xLoop: '''if''' [ x <- x + 1 ] < 100 '''then''' '''begin'''
'''if''' isSemiPrime( x ) '''then''' '''out''' x '''else''' 0;
'''goto''' xLoop
'''end''' '''else''' 0
'''end''' $
<!-- </syntaxhighlight> -->
{{out}}
<pre>
NUMBER 4
NUMBER 6
NUMBER 9
NUMBER 10
...
NUMBER 91
NUMBER 93
NUMBER 94
NUMBER 95
</pre>
=={{header|F_Sharp|F#}}==
<
let rec loop currentN candidateFactor numberOfFactors =
if numberOfFactors > 2 then numberOfFactors
Line 1,132 ⟶ 1,392:
|> Seq.choose (fun n -> if isSemiprime n then Some(n) else None)
|> Seq.toList
|> printfn "%A"</
{{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]
Line 1,140 ⟶ 1,400:
=={{header|Factor}}==
{{works with|Factor|0.98}}
<syntaxhighlight lang="text">USING: io kernel math.primes.factors prettyprint sequences ;
: semiprime? ( n -- ? ) factors length 2 = ;</
Displaying the semiprimes under 100:
<syntaxhighlight lang="text">100 <iota> [ semiprime? ] filter [ bl ] [ pprint ] interleave nl</
{{out}}
<pre>
Line 1,153 ⟶ 1,413:
=={{header|Forth}}==
<
0 swap dup 2 do
begin dup i mod 0= while i / swap 1+ swap repeat
Line 1,160 ⟶ 1,420:
;
: test 100 2 do i semiprime? if i . then loop cr ;</
{{out}}
<pre>
Line 1,168 ⟶ 1,428:
=={{header|Frink}}==
<
=={{header|Go}}==
<
import "fmt"
Line 1,201 ⟶ 1,453:
fmt.Println(v, "->", semiprime(v))
}
}</
{{out}}
<pre>
Line 1,214 ⟶ 1,466:
=={{header|Haskell}}==
{{libheader|Data.Numbers.Primes}}
<
isSemiprime n = (length factors) == 2 && (product factors) == n ||
(length factors) == 1 && (head factors) ^ 2 == n
where factors = primeFactors n</
Alternative (and faster) implementation using pattern matching:
<
isSemiprime n = case (primeFactors n) of
[f1, f2] -> f1 * f2 == n
otherwise -> False</
=={{header|Icon}} and {{header|Unicon}}==
Works in both languages:
<
procedure main(A)
Line 1,236 ⟶ 1,488:
procedure semiprime(n) # Succeeds and produces the factors only if n is semiprime.
return (2 = *(nf := factors(n)), nf)
end</
{{Out}}
Line 1,250 ⟶ 1,502:
Implementation:
<
Example use: find all semiprimes less than 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</
Description: factor the number and count the primes in the factorization, is it 2?
Line 1,264 ⟶ 1,516:
Like the Ada example here, this borrows from [[Prime decomposition#Java|Prime decomposition]] and shows the semiprimes below 100 and from 1675 to 1680.
<
import java.util.ArrayList;
import java.util.List;
Line 1,320 ⟶ 1,572:
}
}
}</
{{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
Line 1,328 ⟶ 1,580:
{{works with|jq}}
'''Works with gojq, the Go implementation of jq'''
<syntaxhighlight lang="jq">
def is_semiprime:
| until( .i > .n or .result;
if .nf == 2 then .result = 0
else .nf += 1
| .n /= .i
end)
| .i += 1)
| if .result == 0 then false else .nf == 2 end;
</syntaxhighlight>
'''Examples'''
<syntaxhighlight lang="jq">
(1679, 1680) | "\(.) => \(is_semiprime)"
</syntaxhighlight>
{{out}}
<pre>
Line 1,359 ⟶ 1,605:
{{works with|Julia|0.6}}
<
issemiprime(n::Integer) = sum(values(factor(n))) == 2
@show filter(issemiprime, 1:100)</
{{out}}
Line 1,368 ⟶ 1,614:
=={{header|Kotlin}}==
{{trans|Go}}
<
fun isSemiPrime(n: Int): Boolean {
Line 1,385 ⟶ 1,631:
for (v in 1675..1680)
println("$v ${if (isSemiPrime(v)) "is" else "isn't"} semi-prime")
}</
{{out}}
Line 1,398 ⟶ 1,644:
=={{header|Ksh}}==
<
#!/bin/ksh
Line 1,434 ⟶ 1,680:
done
echo
</syntaxhighlight>
{{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>
=={{header|Lambdatalk}}==
<syntaxhighlight lang="scheme">
{def factors
{def factors.r
{lambda {:n :i}
{if {> :i :n}
then
else {if {= {% :n :i} 0}
then :i {factors.r {/ :n :i} :i}
else {factors.r :n {+ :i 1}} }}}}
{lambda {:n}
{A.new {factors.r :n 2} }}}
-> factors
{factors 491} -> [491] // prime
{factors 492} -> [2,2,3,41]
{factors 493} -> [17,29] // semiprime
{factors 494} -> [2,13,19]
{factors 495} -> [3,3,5,11]
{factors 496} -> [2,2,2,2,31]
{factors 497} -> [7,71] // semiprime
{factors 498} -> [2,3,83]
{factors 499} -> [499] // prime
{factors 500} -> [2,2,5,5,5]
{S.replace \s by space in
{S.map {lambda {:i}
{let { {:i :i} {:f {factors :i}}
} {if {= {A.length :f} 2}
then :i={A.first :f}*{A.last :f}
else}} }
{S.serie 1 100}}}
->
4 = 2*2
6 = 2*3
9 = 3*3
10 = 2*5
14 = 2*7
15 = 3*5
21 = 3*7
22 = 2*11
25 = 5*5
26 = 2*13
33 = 3*11
34 = 2*17
35 = 5*7
38 = 2*19
39 = 3*13
46 = 2*23
49 = 7*7
51 = 3*17
55 = 5*11
57 = 3*19
58 = 2*29
62 = 2*31
65 = 5*13
69 = 3*23
74 = 2*37
77 = 7*11
82 = 2*41
85 = 5*17
86 = 2*43
87 = 3*29
91 = 7*13
93 = 3*31
94 = 2*47
95 = 5*19
</syntaxhighlight>
=={{header|Lingo}}==
<
div = 2
cnt = 0
Line 1,452 ⟶ 1,768:
end repeat
return cnt=2
end</
<
repeat with i = 1 to 100
if isSemiPrime(i) then res.add(i)
end repeat
put res</
{{out}}
Line 1,466 ⟶ 1,782:
=={{header|Lua}}==
<syntaxhighlight lang="lua">
function semiprime (n)
local divisor, count = 2, 0
Line 1,483 ⟶ 1,799:
print(n, semiprime(n))
end
</syntaxhighlight>
{{out}}
<pre>
Line 1,495 ⟶ 1,811:
=={{header|Maple}}==
<
local fact;
fact := NumberTheory:-Divisors( n ) minus {1, n};
Line 1,504 ⟶ 1,820:
end if;
end proc:
{ seq( SemiPrimes( i ), i = 1..100 ) };</
Output:
<syntaxhighlight 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 }
</syntaxhighlight>
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<
factors = FactorInteger[n] // Transpose;
numfactors = factors[[2]] // Total ;
numfactors == 2
]</
Example use: find all semiprimes less than 100:
<
Position[%, True] // Flatten</
{{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>
=={{header|Maxima}}==
<syntaxhighlight lang="maxima">
/* The first part consider the cases of squares of primes, the second part the remaining cases */
semiprimep(n):=if integerp(sqrt(n)) and primep(sqrt(n)) then true else lambda([x],length(ifactors(x))=2 and unique(map(second,ifactors(x)))=[1])(n)$
/* Example */
sublist(makelist(i,i,100),semiprimep);
</syntaxhighlight>
{{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>
=={{header|MiniScript}}==
<
divisor = 2
primes = 0
Line 1,543 ⟶ 1,872:
if isSemiprime(i) then results.push i
end for
print results</
{{output}}
Line 1,551 ⟶ 1,880:
=={{header|NewLisp}}==
<syntaxhighlight lang="newlisp">
;;; Practically identical to the EchoLisp solution
(define (semiprime? n)
Line 1,561 ⟶ 1,890:
(while (not (semiprime? x)) (-- x))
(println "Biggest semiprime reachable: " x " = " ((factor x) 0) " x " ((factor x) 1))
</syntaxhighlight>
{{output}}
<pre>
Line 1,569 ⟶ 1,898:
=={{header|Nim}}==
<
var
i = 2
Line 1,583 ⟶ 1,912:
for k in 1675..1680:
echo k, (if k.isSemiPrime(): " is" else: " isn’t"), " semi-prime"</
{{output}}
Line 1,596 ⟶ 1,925:
=={{header|Objeck}}==
{{trans|Go}}
<
class SemiPrime {
function : Main(args : String[]) ~ Nil {
Line 1,621 ⟶ 1,950:
return nf = 2;
}
}</
Output:
Line 1,628 ⟶ 1,957:
=={{header|Oforth}}==
<
| i |
0 2 n sqrt asInteger for: i [ while(n i /mod swap 0 &=) [ ->n 1+ ] drop ]
n 1 > ifTrue: [ 1+ ] 2 == ; </
{{out}}
Line 1,640 ⟶ 1,969:
=={{header|PARI/GP}}==
<
A faster version might use trial division and primality testing:
<
forprime(p=2,97,if(n%p==0, return(isprime(n/p))));
if(isprime(n), return(0));
bigomega(n)==2
};</
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:
<
issemiprime(GEN n)
{
Line 1,726 ⟶ 2,055:
avma = ltop;
return 0; /* never used */
}</
=={{header|Pascal}}==
{{libheader|primTrial}}{{works with|Free Pascal}}
<
{$IFDEF FPC}
{$Mode objfpc}// compiler switch to use result
Line 1,771 ⟶ 2,100:
inc(i);
until i> k;
END.</
;output:
<pre>
Line 1,792 ⟶ 2,121:
{{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.
<
for ([1..100], [1675..1681], [2,4,99,100,1679,5030,32768,1234567,9876543,900660121]) {
print join(" ",grep { is_semiprime($_) } @$_),"\n";
}</
{{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
Line 1,802 ⟶ 2,131:
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.
<
print join(" ", grep { scalar factor($_) == 2 } 1..100),"\n";</
While <tt>is_semiprime</tt> is the fastest way, we can do some of its pre-tests by hand, such as:
<
sub issemi {
my $n = shift;
Line 1,814 ⟶ 2,143:
}
2 == factor($n);
}</
=={{header|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;">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: #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>
<!--</
{{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>
=={{header|PHP}}==
{{trans|TypeScript}}
<syntaxhighlight lang="php">
<?php
// Semiprime
function primeFactorsCount($n)
{
$n = abs($n);
$count = 0; // Result
if ($n >= 2)
for ($factor = 2; $factor <= $n; $factor++)
while ($n % $factor == 0) {
$count++;
$n /= $factor;
}
return $count;
}
echo "Enter an integer: ",
$n = (int)fgets(STDIN);
echo (primeFactorsCount($n) == 2 ?
"It is a semiprime.\n" : "It is not a semiprime.\n");
?>
</syntaxhighlight>
{{out}}
<pre>
Enter an integer: 60
It is not a semiprime.
</pre>
<pre>
Enter an integer: 33
It is a semiprime.
</pre>
=={{header|PicoLisp}}==
<
(make
(let
Line 1,850 ⟶ 2,214:
(conc (range 1 100) (range 1675 1680)) ) )
(bye)</
{{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>
=={{header|PL/0}}==
{{trans|Tiny BASIC}}
PL/0 does not handle strings. So, the program waits for entering a number, and then displays 1 if the number is a semiprime, 0 otherwise.
<syntaxhighlight lang="pascal">
var n, count, factor;
begin
? n;
if n < 0 then n := -n;
count := 0;
if n >= 2 then
begin
factor := 2;
while factor <= n do
begin
while (n / factor) * factor = n do
begin
count := count + 1; n := n / factor
end;
factor := factor + 1
end;
end;
if count = 2 then ! 1;
if count <> 2 then ! 0
end.
</syntaxhighlight>
=={{header|PL/I}}==
<
/*--------------------------------------------------------------------
* 22.02.2014 Walter Pachl using the is_prime code from
Line 1,944 ⟶ 2,334:
End spb;
</syntaxhighlight>
'''Output:'''
<pre> 900660121 1 is semiprime 30011*30011
Line 1,956 ⟶ 2,346:
100 0 is NOT semiprime 2*2*25
5040 0 is NOT semiprime 2*2*1260</pre>
=={{header|PL/M}}==
{{Trans|C++}}
{{works with|8080 PL/M Compiler}} ... under CP/M (or an emulator)
<syntaxhighlight lang="plm">
100H: /* FIND SOME SEMI-PRIMES - NUMBERS WITH EXACTLY 2 PRIME FACTORS */
/* CP/M BDOS SYSTEM CALL AND I/O ROUTINES */
BDOS: PROCEDURE( FN, ARG ); DECLARE FN BYTE, ARG ADDRESS; GOTO 5; END;
PR$CHAR: PROCEDURE( C ); DECLARE C BYTE; CALL BDOS( 2, C ); END;
PR$STRING: PROCEDURE( S ); DECLARE S ADDRESS; CALL BDOS( 9, S ); END;
PR$NL: PROCEDURE; CALL PR$CHAR( 0DH ); CALL PR$CHAR( 0AH ); END;
PR$NUMBER: PROCEDURE( N ); /* PRINTS A NUMBER IN THE MINIMUN FIELD WIDTH */
DECLARE N ADDRESS;
DECLARE V ADDRESS, N$STR ( 6 )BYTE, W BYTE;
V = N;
W = LAST( N$STR );
N$STR( W ) = '$';
N$STR( W := W - 1 ) = '0' + ( V MOD 10 );
DO WHILE( ( V := V / 10 ) > 0 );
N$STR( W := W - 1 ) = '0' + ( V MOD 10 );
END;
CALL PR$STRING( .N$STR( W ) );
END PR$NUMBER;
/* TASK */
/* RETURNS TRUE IF V IS SEMI-PRIME, FALSE OTHERWISE */
IS$SEMI$PRIME: PROCEDURE( V )BYTE;
DECLARE V ADDRESS;
DECLARE ( A, B, C ) ADDRESS;
A = 2; B = 0; C = V;
DO WHILE B < 3 AND C > 1;
IF C MOD A = 0 THEN DO;
C = C / A;
B = B + 1;
END;
ELSE A = A + 1;
END;
RETURN B = 2;
END IS$SEMI$PRIME;
DECLARE X ADDRESS;
DO X = 2 TO 99;
IF IS$SEMI$PRIME( X ) THEN DO;
CALL PR$NUMBER( X );
CALL PR$CHAR( ' ' );
END;
END;
EOF
</syntaxhighlight>
{{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>
=={{header|PowerShell}}==
<syntaxhighlight lang="powershell">
function isPrime ($n) {
if ($n -le 1) {$false}
Line 1,984 ⟶ 2,430:
"6: $(semiprime 6)"
$OFS = " "
"semiprime
</syntaxhighlight>
<b>Output:</b>
<pre>
Line 1,993 ⟶ 2,439:
12:
6: 2 x 3
semiprime
</pre>
=={{header|Prolog}}==
works with swi-prolog
<syntaxhighlight lang="prolog">
factors(N, FList):-
factors(N, 2, 0, FList).
factors(1, _, _Count, []).
factors(_, _, Count, []):- Count > 1. % break on 2 factors reached
factors(N, Start, Count, [Fac|FList]):-
N1 is floor(sqrt(N)),
between(Start, N1, Fac),
N mod Fac =:= 0,!,
N2 is N div Fac,
Count1 is Count + 1,
factors(N2, Fac, Count1, FList).
factors(N, _, _, [N]):- N >= 2.
semiPrimeList(Limit, List):-
findall(N, semiPrimes(2, Limit, N), List).
semiPrimes(Start, Limit, N):-
between(Start, Limit, N),
factors(N, [F1, F2]),
N =:= F1 * F2. % correct factors break
do:- semiPrimeList(100, SemiPrimes),
writeln(SemiPrimes),
findall(N, semiPrimes(1675, 1685, N), SemiPrimes2),
writeln(SemiPrimes2).
</syntaxhighlight>
{{out}}
<pre>
?- do.
[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,1681,1685]
true.
</pre>
=={{header|PROMAL}}==
<syntaxhighlight lang="promal">
;;; find some semiprimes - numbers with two prime factors
PROGRAM semiPrimes
INCLUDE library
FUNC BYTE isSemiPrime
ARG WORD n
WORD f
WORD factorCount
BYTE result
BEGIN
f = 2
factorCount = 0
WHILE factorCount < 3 AND n > 1
WHILE n % f = 0
factorCount = factorCount + 1
n = n / f
f = f + 1
IF factorCOunt = 2
result = 1
ELSE
result = 0
RETURN result
END
WORD n
BEGIN
OUTPUT "Semiprimes under 100:#C "
FOR n = 1 TO 99
IF isSemiPrime( n )
OUTPUT " #W", n
OUTPUT "#CSemiprimes between 1670 and 1690:#C "
FOR n = 1670 TO 1690
IF isSemiPrime( n )
OUTPUT " #W", n
END
</syntaxhighlight>
{{out}}
<pre>
Semiprimes under 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
Semiprimes between 1670 and 1690:
1671 1673 1678 1679 1681 1685 1687 1689
</pre>
=={{header|Python}}==
This imports [[Prime decomposition#Python]]
<
def semiprime(n):
Line 2,005 ⟶ 2,536:
return next(d) * next(d) == n
except StopIteration:
return False</
{{out}}
From Idle:
<
True
>>> [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]
>>> </
=={{header|Quackery}}==
<code>
<syntaxhighlight lang
say "Semiprimes less than 100:" cr
100 times [ i^ semiprime if [ i^ echo sp ] ]</
{{out}}
<pre>Semiprimes less than 100:
4 6
=={{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.
<
(require math)
Line 2,045 ⟶ 2,576:
(for/or ((pair (pair-factorize n)))
(for/and ((el pair))
(prime? el))))</
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).
<
(require math)
Line 2,059 ⟶ 2,590:
(= (expt (caar prime-factors) (cadar prime-factors)) n))
(and (= (length prime-factors) 2)
(= (foldl (λ (x y) (* (car x) y)) 1 prime-factors) n)))))</
=={{header|Raku}}==
(formerly Perl 6)
Here is a naive, grossly inefficient implementation.
<syntaxhighlight lang="raku"
not $n.is-prime and
.is-prime given
Line 2,077 ⟶ 2,608:
nok is-semiprime([*] my @f3 = @primes.roll(3)), ~@f3;
nok is-semiprime([*] my @f4 = @primes.roll(4)), ~@f4;
}</
{{out}}
<pre>ok 1 - 17
Line 2,104 ⟶ 2,635:
{{works with|Rakudo|2017.02}}
<syntaxhighlight lang="raku"
return False if $n.is-prime;
my $factor = find-factor( $n );
Line 2,142 ⟶ 2,673:
say 'elapsed seconds: ', now - $start;
</syntaxhighlight>
{{out}}
<pre>Semiprimes less than 100:
Line 2,182 ⟶ 2,713:
=={{header|REXX}}==
===version 1===
<
* 20.02.2014 Walter Pachl relying on 'prime decomposition'
* 21.02.2014 WP Clarification: I copied the algorithm created by
Line 2,237 ⟶ 2,768:
z=z%j /*% (percent) is integer divide.*/
end /*while z··· */ /* // ?---remainder integer ÷.*/
return /*finished, now return to invoker*/</
'''Output'''
<pre>4 is semiprime 2 2
Line 2,251 ⟶ 2,782:
The '''isPrime''' function could be optimized by utilizing an integer square root function instead of testing if '''j*j>x''' for every divisor.
<
parse arg bot top . /*obtain optional arguments from the CL*/
if bot=='' | bot=="," then bot=random() /*None given? User wants us to guess.*/
Line 2,285 ⟶ 2,816:
else return 0
end /*k*/ /* [↑] see if 2nd factor is prime or ¬*/
end /*j*/ /* [↑] J is never a multiple of three.*/</
{{out|output|text= when using the input of: <tt> -1 106 </tt>}}
Line 2,461 ⟶ 2,992:
It gets its speed increase by the use of memoization of the prime numbers found, an unrolled primality (division) check, and other speed improvements.
<
parse arg bot top . /*obtain optional arguments from the CL*/
if bot=='' | bot=="," then bot=random() /*None given? User wants us to guess.*/
Line 2,501 ⟶ 3,032:
end /*k*/ /* [↑] see if 2nd factor is prime or ¬*/
end /*j*/ /* [↑] J is never a multiple of three.*/
return 0</
{{out|output|text= is identical to the previous REXX version.}} <br><br>
=={{header|Ring}}==
<
prime = 1679
decomp(prime)
Line 2,530 ⟶ 3,061:
next
return true
</syntaxhighlight>
=={{header|RPL}}==
<code>PDIV</code> is defined at [[Prime decomposition#RPL|Prime decomposition]]
≪ <span style="color:blue">'''PDIV'''</span> SIZE 2 == ≫ '<span style="color:blue">'''SPR1?'''</span>' STO
≪ { } 1 100 '''FOR''' n '''IF''' n <span style="color:blue">'''SPR1?'''</span> '''THEN''' n + '''END NEXT''' ≫ EVAL
{{out}}
<pre>
1: { 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|Ruby}}==
<
# 75.prime_division # Returns the factorization.75 divides by 3 once and by 5 twice => [[3, 1], [5, 2]]
Line 2,545 ⟶ 3,086:
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]
</syntaxhighlight>
Faster version using 'factor' function from [U|Li]nux Core Utilities library.
<
`factor #{n}`.split
end
n = 2**72 - 1 #4722366482869645213695
(n-50..n).each { |n| puts "#{n} -> #{semiprime(n)}" }</
{{out}}
<pre>4722366482869645213645 -> false
Line 2,607 ⟶ 3,148:
=={{header|Rust}}==
<syntaxhighlight lang="rust">extern crate primal;
fn isqrt(n: usize) -> usize {
Line 2,662 ⟶ 3,203:
fn test6() {
assert_eq!((2..1_000_000).filter(|&n| is_semiprime(n)).count(), 210_035);
}</
functional version of is_semiprime:
<syntaxhighlight lang="rust">fn is_semiprime(n: usize) -> bool {
fn iter(x: usize, start: usize, count: usize) -> usize {
if count > 2 {return count} // break for semi_prime
let limit = (x as f64).sqrt().ceil() as usize;
match (start..=limit).skip_while(|i| x % i > 0).next() {
Some(v) => iter(x / v, v, count + 1),
None => if x < 2 { count }
else { count + 1 }
}
}
iter(n, 2, 0) == 2
}</syntaxhighlight>
{{out}}
<pre>
Line 2,679 ⟶ 3,232:
=={{header|Scala}}==
{{works with|Scala 2.9.1}}
<
def isSP(n: Int): Boolean = {
Line 2,698 ⟶ 3,251:
1675 to 1681 foreach {i => println(i+" -> "+isSP(i))}
}</
{{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
Line 2,710 ⟶ 3,263:
=={{header|Seed7}}==
<
const func boolean: semiPrime (in var integer: n) is func
Line 2,736 ⟶ 3,289:
writeln(v <& " -> " <& semiPrime(v));
end for;
end func;</
{{out}}
Line 2,750 ⟶ 3,303:
=={{header|Sidef}}==
Built-in:
<
say is_semiprime(2**256 - 1) #=> false</
User-defined function, with trial division up to a given bound '''B''':
<
with (n.trial_factor(B)) { |f|
Line 2,764 ⟶ 3,317:
}
say [2,4,99,100,1679,32768,1234567,9876543,900660121].grep(is_semiprime)</
{{out}}
<pre>
Line 2,772 ⟶ 3,325:
=={{header|Swift}}==
<
func primes(n: Int) -> AnyGenerator<Int> {
Line 2,808 ⟶ 3,361:
}
return false
}</
=={{header|Tcl}}==
{{tcllib|math::numtheory}}
<
proc isSemiprime n {
Line 2,835 ⟶ 3,388:
puts "NOT a semiprime"
}
}</
{{out}}
<pre>
Line 2,844 ⟶ 3,397:
1679 is ... a semiprime
1680 is ... NOT a semiprime
</pre>
== {{header|TypeScript}} ==
{{trans|ASIC}}
<syntaxhighlight lang="javascript">
// Semiprime
function primeFactorsCount(n: number): number {
n = Math.abs(n);
var count = 0; // Result
if (n >= 2)
for (factor = 2; factor <= n; factor++)
while n % factor == 0) {
count++;
n /= factor;
}
return count;
}
const readline = require('readline').createInterface({
input: process.stdin, output: process.stdout
});
readline.question('Enter an integer: ', sn => {
var n = parseInt(sn);
console.log(primeFactorsCount(n) == 2 ?
"It is a semiprime." : "It is not a semiprime.");
readline.close();
});
</syntaxhighlight>
{{out}}
<pre>
Enter an integer: 33
It is a semiprime.
</pre>
<pre>
Enter an integer: 60
It is not a semiprime.
</pre>
=={{header|Wren}}==
{{trans|Go}}
<
if (n < 3) return false
var nf = 0
Line 2,863 ⟶ 3,454:
for (v in 1675..1680) {
System.print("%(v) -> %(semiprime.call(v) ? "is" : "is not") semi-prime")
}</
{{out}}
Line 2,876 ⟶ 3,467:
=={{header|XPL0}}==
<
int N, F, C;
[C:= 0; F:= 2;
Line 2,892 ⟶ 3,483:
if Semiprime(N) then
[IntOut(0, N); ChOut(0, ^ )];
]</
{{out}}
Line 2,901 ⟶ 3,492:
=={{header|zkl}}==
{{trans|C}}
<
reg f = 0;
p:=2; while(f < 2 and p*p <= n){
Line 2,908 ⟶ 3,499:
}
return(f + (n > 1) == 2);
}</
{{out}}
<pre>
| |||