Semiprime
You are encouraged to solve this task according to the task description, using any language you may know.
Semiprime numbers are natural numbers that are products of exactly two (possibly equal) prime numbers.
Semiprimes are also known as:
- semi-primes
- biprimes
- bi-primes
- 2-almost primes
- or simply: P2
- Example
1679 = 23 × 73
(This particular number was chosen as the length of the Arecibo message).
- Task
Write a function determining whether a given number is semiprime.
- See also
- The Wikipedia article: semiprime.
- The Wikipedia article: almost prime.
- The OEIS sequence: A001358: semiprimes which has a shorter definition: the product of two primes.
F is_semiprime(=c)
V a = 2
V b = 0
L b < 3 & c != 1
I c % a == 0
c /= a
b++
E
a++
R b == 2
print((1..100).filter(n -> is_semiprime(n)))- Output:
[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]
* Semiprime 14/03/2017
SEMIPRIM CSECT
USING SEMIPRIM,R13 base register
B 72(R15) skip savearea
DC 17F'0' savearea
STM R14,R12,12(R13) save previous context
ST R13,4(R15) link backward
ST R15,8(R13) link forward
LR R13,R15 set addressability
LA R10,PG pgi=0
LA R8,0 m=0
L R6,=F'2' i=2
DO WHILE=(C,R6,LE,=F'100') do i=2 to 100
ST R6,N n=i
LA R9,0 f=0
LA R7,2 j=2
LOOPJ EQU * do j=2 while f<2 and j*j<=n
C R9,=F'2' if f<2
BNL EXITJ then exit do j
LR R5,R7 j
MR R4,R7 *j
C R5,N if j*j<=n
BH EXITJ then exit do j
LOOPK EQU * do while n mod j=0
L R4,N n
SRDA R4,32 ~
DR R4,R7 /j
LTR R4,R4 if n mod <>0
BNZ EXITK then exit do j
ST R5,N n=n/j
LA R9,1(R9) f=f+1
B LOOPK enddo k
EXITK LA R7,1(R7) j++
B LOOPJ enddo j
EXITJ L R4,N n
IF C,R4,GT,=F'1' THEN if n>1 then
LA R2,1 g=1
ELSE , else
LA R2,0 g=0
ENDIF , endif
AR R2,R9 +f
IF C,R2,EQ,=F'2' THEN if f+(n>1)=2 then
XDECO R6,XDEC edit i
MVC 0(5,R10),XDEC+7 output i
LA R10,5(R10) pgi=pgi+10
LA R8,1(R8) m=m+1
LR R4,R8 m
SRDA R4,32 ~
D R4,=F'16' m/16
IF LTR,R4,Z,R4 THEN if m mod 16=0 then
XPRNT PG,L'PG print buffer
MVC PG,=CL80' ' clear buffer
LA R10,PG pgi=0
ENDIF , endif
ENDIF , endif
LA R6,1(R6) i++
ENDDO , enddo i
XPRNT PG,L'PG print buffer
MVC PG,=CL80'..... semiprimes' init buffer
XDECO R8,XDEC edit m
MVC PG(5),XDEC+7 output m
XPRNT PG,L'PG print buffer
L R13,4(0,R13) restore previous savearea pointer
LM R14,R12,12(R13) restore previous context
XR R15,R15 rc=0
BR R14 exit
N DS F n
PG DC CL80' ' buffer
XDEC DS CL12 temp
YREGS
END SEMIPRIM- Output:
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 34 semiprimes
BYTE FUNC IsSemiPrime(INT n)
INT a,b
a=2 b=0
WHILE b<3 AND n#1
DO
IF n MOD a=0 THEN
n==/a b==+1
ELSE
a==+1
FI
OD
IF b=2 THEN
RETURN(1)
FI
RETURN(0)
PROC Main()
INT i
PrintE("Semiprimes:")
FOR i=1 TO 500
DO
IF IsSemiPrime(i) THEN
PrintI(i) Put(32)
FI
OD
RETURN- Output:
Screenshot from Atari 8-bit computer
Semiprimes: 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 106 111 115 118 119 121 122 123 129 133 134 141 142 143 145 146 155 158 159 161 166 169 177 178 183 185 187 194 201 202 203 205 206 209 213 214 215 217 218 219 221 226 235 237 247 249 253 254 259 262 265 267 274 278 287 289 291 295 298 299 301 302 303 305 309 314 319 321 323 326 327 329 334 335 339 341 346 355 358 361 362 365 371 377 381 382 386 391 393 394 395 398 403 407 411 413 415 417 422 427 437 445 446 447 451 453 454 458 466 469 471 473 478 481 482 485 489 493 497
This imports the package Prime_Numbers from Prime decomposition#Ada.
with Prime_Numbers, Ada.Text_IO;
procedure Test_Semiprime is
package Integer_Numbers is new
Prime_Numbers (Natural, 0, 1, 2);
use Integer_Numbers;
begin
for N in 1 .. 100 loop
if Decompose(N)'Length = 2 then -- N is a semiprime;
Ada.Text_IO.Put(Integer'Image(Integer(N)));
end if;
end loop;
Ada.Text_IO.New_Line;
for N in 1675 .. 1680 loop
if Decompose(N)'Length = 2 then -- N is a semiprime;
Ada.Text_IO.Put(Integer'Image(Integer(N)));
end if;
end loop;
end Test_Semiprime;
It outputs all semiprimes below 100 and all semiprimes between 1675 and 1680:
- Output:
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
Note that
1675 = 5 * 5 * 67, 1676 = 2 * 2 * 419, 1677 = 3 * 13 * 43, 1678 = 2 * 839, 1679 = 23 * 73, 1680 = 2 * 2 * 2 * 2 * 3 * 5 * 7,
so the result printed is actually correct.
begin
comment - return a mod b;
integer procedure mod(a, b);
value a, b; integer a, b;
begin
mod := a - entier(a/b) * b;
end;
comment - return true if n is a semi-prime number;
boolean procedure semiprime(n);
value n; integer n;
begin
integer i, count;
count := 1;
i := 2;
for i := i while (i * i) <= n do
begin
if mod(n, i) = 0 then
begin
count := count + 1;
n := n / i;
end
else
i := i + 1;
end;
semiprime := (count = 2);
end;
integer i, limit, found;
limit := 100;
outstring(1,"Searching up to");
outinteger(1,limit);
outstring(1,"for semi-primes:\n");
found := 0;
for i := 3 step 1 until limit do
begin
if semiprime(i) then
begin
outinteger(1,i);
found := found + 1;
if mod(found, 10) = 0 then outstring(1,"\n");
end;
end;
outstring(1,"\n");
outinteger(1,found);
outstring(1,"were found");
end- Output:
Searching up to 100 for semi-primes: 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 34 were found
# returns TRUE if n is semi-prime, FALSE otherwise #
# n is semi prime if it has exactly two prime factors #
PROC is semiprime = ( INT n )BOOL:
BEGIN
# We only need to consider factors between 2 and #
# sqrt( n ) inclusive. If there is only one of these #
# then it must be a prime factor and so the number #
# is semi prime #
INT factor count := 0;
FOR factor FROM 2 TO ENTIER sqrt( ABS n )
WHILE factor count < 2 DO
IF n MOD factor = 0 THEN
factor count +:= 1;
# check the factor isn't a repeated factor #
IF n /= factor * factor THEN
# the factor isn't the square root #
INT other factor = n OVER factor;
IF other factor MOD factor = 0 THEN
# have a repeated factor #
factor count +:= 1
FI
FI
FI
OD;
factor count = 1
END # is semiprime # ;
# determine the first few semi primes #
print( ( "semi primes below 100:", newline, " " ) );
FOR i TO 99 DO
IF is semi prime( i ) THEN print( ( " ", whole( i, 0 ) ) ) FI
OD;
print( ( newline ) );
print( ( "semi primes between 1670 and 1690: " ) );
FOR i FROM 1670 TO 1690 DO
IF is semi prime( i ) THEN print( ( whole( i, 0 ), " " ) ) FI
OD;
print( ( newline ) )- Output:
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 between 1670 and 1690: 1671 1673 1678 1679 1681 1685 1687 1689
begin
comment - return a mod b;
integer function mod(a, b);
integer a, b;
begin
mod := a - (a/b) * b;
end;
comment - return 1 if n is semi-prime, otherwise 0;
integer function semiprime(n);
integer n;
begin
integer i, count;
count := 1;
i := 2;
while (i * i) <= n do
begin
if mod(n, i) = 0 then
begin
count := count + 1;
n := n / i;
end
else
i := i + 1;
end;
semiprime := (if count = 2 then 1 else 0);
end;
integer i, limit, found;
limit := 100;
found := 0;
for i := 3 step 1 until limit do
begin
if semiprime(i) = 1 then
begin
writeon(i);
found := found + 1;
if mod(found, 10) = 0 then write("");
end;
end;
write(found, " were found");
end- Output:
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
34 were found
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.- Output:
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
semiPrime?: function [x][
2 = size factors.prime x
]
print select 1..100 => semiPrime?
- Output:
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
SetBatchLines -1
k := 1
loop, 100
{
m := semiprime(k)
StringSplit, m_m, m, -
if ( m_m1 = "yes" )
list .= k . " "
k++
}
MsgBox % list
list :=
;===================================================================================================================================
k := 1675
loop, 5
{
m := semiprime(k)
StringSplit, m_m, m, -
if ( m_m1 = "yes" )
list1 .= semiprime(k) . "`n"
else
list1 .= semiprime(k) . "`n"
k++
}
MsgBox % list1
list1 :=
;===================================================================================================================================
; The function==========================================================================================================================
semiprime(k)
{
start := floor(sqrt(k))
loop, % floor(sqrt(k)) - 1
{
if ( mod(k, start) = 0 )
new .= floor(start) . "*" . floor(k//start) . ","
start--
}
StringSplit, index, new, `,
if ( index0 = 2 )
{
StringTrimRight, new, new, 1
StringSplit, 2_ind, new, *
if (mod(2_ind2, 2_ind1) = 0) && ( 2_ind1 != 2_ind2 )
new := "N0- " . k . " - " . new
else
new := "yes- " . k . " - " . new
}
else
new := "N0- " . k . " - " . new
return new
}
;=================================================================================================================================================
esc::Exitapp
- Output:
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 N0- 1675 - 25*67,5*335, N0- 1676 - 4*419,2*838, N0- 1677 - 39*43,13*129,3*559, yes- 1678 - 2*839 yes- 1679 - 23*73
# syntax: GAWK -f SEMIPRIME.AWK
BEGIN {
main(0,100)
main(1675,1680)
exit(0)
}
function main(lo,hi, i) {
printf("%d-%d:",lo,hi)
for (i=lo; i<=hi; i++) {
if (is_semiprime(i)) {
printf(" %d",i)
}
}
printf("\n")
}
function is_semiprime(n, i,nf) {
nf = 0
for (i=2; i<=n; i++) {
while (n % i == 0) {
if (nf == 2) {
return(0)
}
nf++
n /= i
}
}
return(nf == 2)
}
- Output:
0-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 1675-1680: 1678 1679
100 REM Semiprime
110 DECLARE EXTERNAL FUNCTION FactorsCnt
120 INPUT PROMPT "Enter an integer: ": N
130 IF FactorsCnt(N) = 2 THEN
140 PRINT "It is a semiprime."
150 ELSE
160 PRINT "It is not a semiprime."
170 END IF
180 END
190 REM
200 EXTERNAL FUNCTION FactorsCnt(N)
210 LET AN = ABS(N)
220 LET Count = 0
230 IF AN >= 2 THEN
240 FOR F = 2 TO AN
250 DO WHILE MOD(AN, F) = 0
260 LET Count = Count + 1
270 LET AN = INT(AN / F)
280 LOOP
290 NEXT F
300 END IF
310 LET FactorsCnt = Count
320 END FUNCTION
- Output:
(2 samples)
Enter an integer: 60 It is not a semiprime.
Enter an integer: 33 It is a semiprime.
REM Semiprime
PRINT "Enter an integer ";
INPUT N
N = ABS(N)
Count = 0
IF N >= 2 THEN
FOR Factor = 2 TO N
NModFactor = N MOD Factor
WHILE NModFactor = 0
Count = Count + 1
N = N / Factor
NModFactor = N MOD Factor
WEND
NEXT Factor
ENDIF
IF Count = 2 THEN
PRINT "It is a semiprime."
ELSE
PRINT "It is not a semiprime."
ENDIF
END
- Output:
Enter an integer ?60 It is not a semiprime.
Enter an integer ?33 It is a semiprime.
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
end while
if c = 2 then return "True"
return "False"
end function
for i = 0 to 64
print i, semiprime$(i)
next i
end100 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
function semiprime( n as uinteger ) as boolean
dim as uinteger a = 2, c = 0
while c < 3 andalso n > 1
if n mod a = 0 then
n /= a
c += 1
else
a += 1
end if
wend
if c = 2 then return true
return false
end function
for i as uinteger = 0 to 64
print i, semiprime(i)
next i
10 INPUT "Enter a number: ", N
20 N=ABS(N)
30 C = 0
40 IF N < 3 THEN GOTO 80
50 F = 2
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."
10 REM Semiprime
20 PRINT "Enter an integer";
30 INPUT N
40 LET N = ABS(N)
50 LET C = 0
60 IF N < 2 THEN 130
70 FOR F = 2 TO N
80 IF INT(N/F)*F <> N THEN 120
90 LET C = C+1
100 LET N = N/F
110 GOTO 80
120 NEXT F
130 IF C <> 2 THEN 160
140 PRINT "It is a semiprime."
150 GOTO 170
160 PRINT "It is not a semiprime."
170 END
Calculations are taken in a subroutine.
' Semiprime
BEGIN DEF
pointer word PtrCount~)
SUB CalcCount(N%, PtrCount~)
BEGIN CODE
PRINT "Enter an integer: "
INPUT (TmpStr$)
N% = VAL(TmpStr$)
PRINT "\n"
CALL CalcCount(N%, VARPTR(Count%))
IF Count% = 2 THEN
PRINT "It is a semiprime.\n"
ELSE
PRINT "It is not a semiprime.\n"
ENDIF
END
SUB CalcCount(N%, PtrCount~)
N% = ABS(N%)
Count% = 0
IF N% >= 2 THEN
FOR Factor% = 2 TO N%
NModFactor% = N% MOD Factor%
WHILE NModFactor% = 0
Count% = Count% + 1
N% = N% \ Factor%
NModFactor% = N% MOD Factor%
WEND
NEXT
ENDIF
[PtrCount~] = Count%
END SUB
- Output:
Enter an integer: 60 It is not a semiprime.
Enter an integer: 33 It is a semiprime.
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
- Output:
2 runs.
ENTER AN INTEGER:60 IT IS NOT A SEMIPRIME.
ENTER AN INTEGER:33 IT IS A SEMIPRIME.
Procedure.s semiprime(n.i)
a.i = 2
c.i = 0
While c < 3 And n > 1
If (n % a) = 0
n / a
c + 1
Else
a + 1
EndIf
Wend
If c = 2
ProcedureReturn "True" ;#True
EndIf
ProcedureReturn "False" ;#False
EndProcedure
OpenConsole()
For i.i = 0 To 64
PrintN(Str(i) + #TAB$ + semiprime(i))
Next i
PrintN(#CRLF$ + "--- terminado, pulsa RETURN---"): Input()
CloseConsole()
End
' Semiprime
DECLARE FUNCTION Count% (BYVAL N%)
INPUT "Enter an integer: ", N%
IF Count%(N%) = 2 THEN
PRINT "It is a semiprime."
ELSE
PRINT "It is not a semiprime."
END IF
END
FUNCTION Count% (BYVAL N%)
N% = ABS(N%)
Result% = 0
IF N% >= 2 THEN
FOR Factor% = 2 TO N%
WHILE N% MOD Factor% = 0
Result% = Result% + 1
N% = N% \ Factor%
WEND
NEXT Factor%
END IF
Count% = Result%
END FUNCTION
- Output:
Enter an integer: 33 It is a semiprime.
Enter an integer: 60 It is not a semiprime.
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
10 REM Semiprime
20 PRINT "Enter an integer"
30 INPUT N
40 IF N < 0 THEN LET N = -N
50 IF N < 2 THEN GOTO 120
60 LET C = 0
70 LET F = 2
80 IF (N / F) * F = N THEN GOTO 150
90 LET F = F + 1
100 IF F > N THEN GOTO 120
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
- Output:
2 runs.
Enter an integer ? 60 It is not a semiprime.
Enter an integer ? 33 It is a semiprime.
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
sub semiprime$ (n)
a = 2
c = 0
while c < 3 and n > 1
if mod(n, a) = 0 then
n = n / a
c = c + 1
else
a = a + 1
end if
wend
if c = 2 then return "True" : fi
return "False"
end sub
for i = 0 to 64
print i, chr$(9), semiprime$(i)
next i
endWhen 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).
semiprime=
m n a b
. 2^-64:?m
& 2*!m:?n
& !arg^!m
: (#%?a^!m*#%?b^!m|#%?a^!n&!a:?b)
& (!a.!b);Test with numbers < 2^63:
2^63:?u
& whl
' ( -1+!u:>2:?u
& ( semiprime$!u:?R&out$(!u ":" !R)
|
)
);Output:
9223372036854775797 : (3.3074457345618258599) 9223372036854775777 : (584911.15768846947407) 9223372036854775771 : (19.485440633518672409) 9223372036854775753 : (266416229.34620158357) 9223372036854775727 : (11113.829962389710679) 9223372036854775717 : (59.156328339607708063) 9223372036854775715 : (5.1844674407370955143) 9223372036854775703 : (9648151.955973018753) 9223372036854775694 : (2.4611686018427387847) 9223372036854775691 : (37.249280325320399343) 9223372036854775687 : (1303.7078566413549329) 9223372036854775685 : (5.1844674407370955137) 9223372036854775673 : (175934777.52424950849) 9223372036854775634 : (2.4611686018427387817) 9223372036854775633 : (421741.21869754273013) 9223372036854775627 : (6277.1469391753521551) 9223372036854775609 : (172153.53576597775553) 9223372036854775601 : (1045692671.8820346831) 9223372036854775589 : (563.16382543582335303) 9223372036854775577 : (267017141.34542246997) 9223372036854775574 : (2.4611686018427387787) 9223372036854775571 : (1951.4727510013764621) 9223372036854775537 : (47.196241958230952671) 9223372036854775531 : (1677122561.5499521771) 9223372036854775522 : (2.4611686018427387761) 9223372036854775511 : (29305709.314729530579) 9223372036854775502 : (2.4611686018427387751) 9223372036854775489 : (9413717.979780041917) 9223372036854775474 : (2.4611686018427387737) 9223372036854775466 : (2.4611686018427387733) 9223372036854775461 : (3.3074457345618258487) 9223372036854775451 : (545369243.16912160257) 9223372036854775439 : (11380717.810438572267) 9223372036854775418 : (2.4611686018427387709) 9223372036854775411 : (1420967.6490912200533) 9223372036854775409 : (15060911.612404657119) 9223372036854775407 : (3.3074457345618258469) 9223372036854775402 : (2.4611686018427387701) 9223372036854775389 : (3.3074457345618258463) 9223372036854775385 : (5.1844674407370955077) 9223372036854775383 : (3.3074457345618258461) 9223372036854775381 : (683.13504205031998207) 9223372036854775379 : (43.214497024112901753) 9223372036854775357 : (17.542551296285575021) 9223372036854775355 : (5.1844674407370955071) ^CTerminate batch job (Y/N)? Y
#include <stdio.h>
int semiprime(int n)
{
int p, f = 0;
for (p = 2; f < 2 && p*p <= n; p++)
while (0 == n % p)
n /= p, f++;
return f + (n > 1) == 2;
}
int main(void)
{
int i;
for (i = 2; i < 100; i++)
if (semiprime(i)) printf(" %d", i);
putchar('\n');
return 0;
}
- Output:
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
static void Main(string[] args)
{
//test some numbers
for (int i = 0; i < 50; i++)
{
Console.WriteLine("{0}\t{1} ", i,isSemiPrime(i));
}
Console.ReadLine();
}
//returns true or false depending if input was considered semiprime
private static bool isSemiPrime(int c)
{
int a = 2, b = 0;
while (b < 3 && c != 1)
{
if ((c % a) == 0)
{
c /= a;
b++;
}
else
{
a++;
};
}
return b == 2;
}
- Output:
0 False 1 False 2 False 3 False 4 True 5 False 6 True 7 False 8 False 9 True 10 True 11 False 12 False 13 False 14 True 15 True 16 False 17 False 18 False 19 False 20 False 21 True 22 True 23 False 24 False 25 True 26 True 27 False 28 False 29 False 30 False 31 False 32 False 33 True 34 True 35 True 36 False 37 False 38 True 39 True 40 False 41 False 42 False 43 False 44 False 45 False 46 True 47 False 48 False 49 True
#include <iostream>
bool isSemiPrime( int c )
{
int a = 2, b = 0;
while( b < 3 && c != 1 )
{
if( !( c % a ) )
{ c /= a; b++; }
else a++;
}
return b == 2;
}
int main( int argc, char* argv[] )
{
for( int x = 2; x < 100; x++ )
if( isSemiPrime( x ) )
std::cout << x << " ";
return 0;
}
- Output:
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
(ns example
(:gen-class))
(defn semi-prime? [n]
(loop [a 2
b 0
c n]
(cond
(> b 2) false
(<= c 1) (= b 2)
(= 0 (rem c a)) (recur a (inc b) (int (/ c a)))
:else (recur (inc a) b c))))
(println (filter semi-prime? (range 1 100)))
- Output:
(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)
(defun semiprimep (n &optional (a 2))
(cond ((> a (isqrt n)) nil)
((zerop (rem n a)) (and (primep a) (primep (/ n a))))
(t (semiprimep n (+ a 1)))))
(defun primep (n &optional (a 2))
(cond ((> a (isqrt n)) t)
((zerop (rem n a)) nil)
(t (primep n (+ a 1)))))
Example Usage:
CL-USER> (semiprimep 1234567) T CL-USER> (semiprimep 9876543) NIL
def semiprime(n)
nf = 0
(2..n).each do |i|
while n % i == 0
return false if nf == 2
nf += 1
n /= i
end
end
nf == 2
end
(1675..1681).each { |n| puts "#{n} -> #{semiprime(n)}" }
- Output:
1675 -> false 1676 -> false 1677 -> false 1678 -> true 1679 -> true 1680 -> false 1681 -> true
Faster version using 'factor' function from [U|Li]nux Core Utilities library.
def semiprime(n)
`factor #{n}`.split(' ').size == 3
end
n = 0xffffffffffffffff_u64 # 2**64 - 1 = 18446744073709551615
(n-50..n).each { |n| puts "#{n} -> #{semiprime(n)}" }
- Output:
18446744073709551565 -> false 18446744073709551566 -> true 18446744073709551567 -> false 18446744073709551568 -> false 18446744073709551569 -> false 18446744073709551570 -> false 18446744073709551571 -> false 18446744073709551572 -> false 18446744073709551573 -> false 18446744073709551574 -> false 18446744073709551575 -> false 18446744073709551576 -> false 18446744073709551577 -> true 18446744073709551578 -> false 18446744073709551579 -> false 18446744073709551580 -> false 18446744073709551581 -> false 18446744073709551582 -> false 18446744073709551583 -> false 18446744073709551584 -> false 18446744073709551585 -> false 18446744073709551586 -> false 18446744073709551587 -> false 18446744073709551588 -> false 18446744073709551589 -> false 18446744073709551590 -> false 18446744073709551591 -> false 18446744073709551592 -> false 18446744073709551593 -> false 18446744073709551594 -> false 18446744073709551595 -> false 18446744073709551596 -> false 18446744073709551597 -> true 18446744073709551598 -> false 18446744073709551599 -> false 18446744073709551600 -> false 18446744073709551601 -> true 18446744073709551602 -> false 18446744073709551603 -> false 18446744073709551604 -> false 18446744073709551605 -> false 18446744073709551606 -> false 18446744073709551607 -> false 18446744073709551608 -> false 18446744073709551609 -> false 18446744073709551610 -> false 18446744073709551611 -> false 18446744073709551612 -> false 18446744073709551613 -> false 18446744073709551614 -> false 18446744073709551615 -> false
bool semiprime(long n) pure nothrow @safe @nogc {
auto nf = 0;
foreach (immutable i; 2 .. n + 1) {
while (n % i == 0) {
if (nf == 2)
return false;
nf++;
n /= i;
}
}
return nf == 2;
}
void main() {
import std.stdio;
foreach (immutable n; 1675 .. 1681)
writeln(n, " -> ", n.semiprime);
}
- Output:
1675 -> false 1676 -> false 1677 -> false 1678 -> true 1679 -> true 1680 -> false
Given a file primes.txt is the list of primes up to the sqrt(2^31-1), i.e. 46337;
$ p1 = f$integer( p1 )
$ if p1 .lt. 2
$ then
$ write sys$output "out of range 2 thru 2^31-1"
$ exit
$ endif
$
$ close /nolog primes
$ on control_y then $ goto clean
$ open primes primes.txt
$
$ loop1:
$ read /end_of_file = prime primes prime
$ prime = f$integer( prime )
$ loop2:
$ t = p1 / prime
$ if t * prime .eq. p1
$ then
$ if f$type( factorization ) .eqs. ""
$ then
$ factorization = f$string( prime )
$ else
$ factorization = factorization + "*" + f$string( prime )
$ endif
$ if t .eq. 1 then $ goto done
$ p1 = t
$ goto loop2
$ else
$ goto loop1
$ endif
$ prime:
$ if f$type( factorization ) .eqs. ""
$ then
$ factorization = f$string( p1 )
$ else
$ factorization = factorization + "*" + f$string( p1 )
$ endif
$ done:
$ show symbol factorization
$ if f$locate( "*", factorization ) .eq. f$length( factorization )
$ then
$ write sys$output "so, it is prime"
$ else
$ if f$element( 2, "*", factorization ) .eqs. "*" then $ write sys$output "so, it is semiprime"
$ endif
$
$ clean:
$ close primes
- Output:
$ @factor 6 FACTORIZATION = "2*3" so, it is semiprime $ @factor 11 FACTORIZATION = "11" so, it is prime $ @factor 2147483646 FACTORIZATION = "2*3*3*7*11*31*151*331"
{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;
- Output:
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.
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 & " "
.
.
(lib 'math)
(define (semi-prime? n)
(= (length (prime-factors n)) 2))
(for ((i 100))
(when (semi-prime? i) (write i)))
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
(lib 'bigint)
(define N (* (random-prime 10000000) (random-prime 10000000)))
→ 6764578882969
(semi-prime? N)
→ #t
;; a pair n,n+1 of semi-primes
(prime-factors 100000000041)
→ (3 33333333347)
(prime-factors 100000000042)
→ (2 50000000021)
defmodule Prime do
def semiprime?(n), do: length(decomposition(n)) == 2
def decomposition(n), do: decomposition(n, 2, [])
defp decomposition(n, k, acc) when n < k*k, do: Enum.reverse(acc, [n])
defp decomposition(n, k, acc) when rem(n, k) == 0, do: decomposition(div(n, k), k, [k | acc])
defp decomposition(n, k, acc), do: decomposition(n, k+1, acc)
end
IO.inspect Enum.filter(1..100, &Prime.semiprime?(&1))
Enum.each(1675..1680, fn n ->
:io.format "~w -> ~w\t~s~n", [n, Prime.semiprime?(n), Prime.decomposition(n)|>Enum.join(" x ")]
end)
- Output:
[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] 1675 -> false 5 x 5 x 67 1676 -> false 2 x 2 x 419 1677 -> false 3 x 13 x 43 1678 -> true 2 x 839 1679 -> true 23 x 73 1680 -> false 2 x 2 x 2 x 2 x 3 x 5 x 7
Another using prime factors from Prime_decomposition#Erlang :
-module(factors).
-export([factors/1,kthfactor/2]).
factors(N) ->
factors(N,2,[]).
factors(1,_,Acc) -> Acc;
factors(N,K,Acc) when N rem K == 0 ->
factors(N div K,K, [K|Acc]);
factors(N,K,Acc) ->
factors(N,K+1,Acc).
% is integer N factorable into M primes?
kthfactor(N,M) ->
case length(factors(N)) of M ->
factors(N);
_ ->
false end.
{out}
17> factors:kthfactor(1679,2).
[73,23]
18> factors:kthfactor(1679,4).
false
23> FS = [{X,factors:kthfactor(X,2)} || X <- lists:seq(50,500), factors:kthfactor(X,2) =/= false].
[{51,[17,3]},
{55,[11,5]},
{57,[19,3]},
{58,[29,2]},
{62,[31,2]},
{65,[13,5]},
{69,[23,3]},
{74,[37,2]},
{77,[11,7]},
{82,[41,2]},
{85,[17,5]},
{86,[43,2]},
{87,[29,3]},
{91,[13,7]},
{93,[31,3]},
{94,[47,2]},
{95,[19,5]},
{106,[53,2]},
{111,[37,3]},
{115,[23,5]},
{118,[59,2]},
{119,[17,7]},
{121,"\v\v"},
{122,[61,2]},
{123,[41,3]},
{129,[43|...]},
{133,[...]},
{134,...},
{...}|...]
Note, there is some junk character data in the output since we 'usually' have to filter for char sequences (it's not a bug, it's a feature!).
PROGRAM SEMIPRIME_NUMBER
!VAR I%
PROCEDURE SEMIPRIME(N%->RESULT%)
LOCAL F%,P%
P%=2
LOOP
EXIT IF NOT(F%<2 AND P%*P%<=N%)
WHILE (N% MOD P%)=0 DO
N%=N% DIV P%
F%+=1
END WHILE
P%+=1
END LOOP
RESULT%=F%-(N%>1)=2
END PROCEDURE
BEGIN
PRINT(CHR$(12);) !CLS
FOR I%=2 TO 100 DO
SEMIPRIME(I%->RESULT%)
IF RESULT% THEN PRINT(I%;) END IF
END FOR
PRINT
END PROGRAM
Output is the same of "C" version.
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 $
- Output:
NUMBER 4
NUMBER 6
NUMBER 9
NUMBER 10
...
NUMBER 91
NUMBER 93
NUMBER 94
NUMBER 95
let isSemiprime (n: int) =
let rec loop currentN candidateFactor numberOfFactors =
if numberOfFactors > 2 then numberOfFactors
elif currentN = candidateFactor then numberOfFactors+1
elif currentN % candidateFactor = 0 then loop (currentN/candidateFactor) candidateFactor (numberOfFactors+1)
else loop currentN (candidateFactor+1) numberOfFactors
if n < 2 then false else 2 = loop n 2 0
seq { 1 .. 100 } |> Seq.choose (fun n -> if isSemiprime n then Some(n) else None)
|> Seq.toList |> printfn "%A"
seq { 1675 .. 1680 }
|> Seq.choose (fun n -> if isSemiprime n then Some(n) else None)
|> Seq.toList
|> printfn "%A"
- Output:
[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]
USING: io kernel math.primes.factors prettyprint sequences ;
: semiprime? ( n -- ? ) factors length 2 = ;
Displaying the semiprimes under 100:
100 <iota> [ semiprime? ] filter [ bl ] [ pprint ] interleave nl
- Output:
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
: semiprime?
0 swap dup 2 do
begin dup i mod 0= while i / swap 1+ swap repeat
over 1 > over i dup * < or if leave then
loop 1 > abs + 2 =
;
: test 100 2 do i semiprime? if i . then loop cr ;
- Output:
test 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 ok
isSemiprime[n] := length[factorFlat[n]] == 2
FB 7.0.35 macOS 14.7.2 Sonoma
include "NSLog.incl"
BOOL local fn Semiprime( n as int )
int a = 2, c = 0
while ( c < 3 && n > 1 )
if ( n % a ) == 0
n = n / a
c++
else
a++
end if
wend
if ( c == 2 ) then return YES
end fn = NO
void local fn FindSemiprimes( limit as int )
NSLog( @"Semiprimes between 0 and %d:\n", limit )
int count = 0
for int i = 1 to limit
if ( fn Semiprime(i) == YES ) then NSLog( @"%4d\b", i ) : count++ : if count % 10 == 0 then NSLog( @"" )
next
end fn
fn FindSemiprimes( 100 )
HandleEvents- Output:
Semiprimes between 0 and 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
package main
import "fmt"
func semiprime(n int) bool {
nf := 0
for i := 2; i <= n; i++ {
for n%i == 0 {
if nf == 2 {
return false
}
nf++
n /= i
}
}
return nf == 2
}
func main() {
for v := 1675; v <= 1680; v++ {
fmt.Println(v, "->", semiprime(v))
}
}
- Output:
1675 -> false 1676 -> false 1677 -> false 1678 -> true 1679 -> true 1680 -> false
isSemiprime :: Int -> Bool
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 :: Int -> Bool
isSemiprime n = case (primeFactors n) of
[f1, f2] -> f1 * f2 == n
otherwise -> False
pfcHelper :: (int * int * int) -> int
pfcHelper x = match x with
| (n, p, count) -> if (p * p > n) then (if (n > 1) then count + 1 else count) else if (n % p == 0) then pfcHelper((n / p, p, count + 1)) else pfcHelper((n, p + 1, count))
primeFactorCount :: int -> int
primeFactorCount n = pfcHelper((n, 2, 0))
isSemiprime :: int -> bool
isSemiprime n = primeFactorCount(n) == 2
[n | n <- [2..100], isSemiprime(n)]
- Output:
[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]
Works in both languages:
link "factors"
procedure main(A)
every nf := semiprime(n := !A) do write(n," = ",nf[1]," * ",nf[2])
end
procedure semiprime(n) # Succeeds and produces the factors only if n is semiprime.
return (2 = *(nf := factors(n)), nf)
end
- Output:
->semiprime 1676 1677 1678 1679 1680 1678 = 2 * 839 1679 = 23 * 73 ->
Implementation:
isSemiPrime=: 2 = #@q: ::0:"0
Example use: find all semiprimes less than 100:
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
Description: factor the number and count the primes in the factorization, is it 2?
Inspired by: #Ada
Like the Ada example here, this borrows from Prime decomposition and shows the semiprimes below 100 and from 1675 to 1680.
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;
public class SemiPrime{
private static final BigInteger TWO = BigInteger.valueOf(2);
public static List<BigInteger> primeDecomp(BigInteger a){
// impossible for values lower than 2
if(a.compareTo(TWO) < 0){
return null;
}
//quickly handle even values
List<BigInteger> result = new ArrayList<BigInteger>();
while(a.and(BigInteger.ONE).equals(BigInteger.ZERO)){
a = a.shiftRight(1);
result.add(TWO);
}
//left with odd values
if(!a.equals(BigInteger.ONE)){
BigInteger b = BigInteger.valueOf(3);
while(b.compareTo(a) < 0){
if(b.isProbablePrime(10)){
BigInteger[] dr = a.divideAndRemainder(b);
if(dr[1].equals(BigInteger.ZERO)){
result.add(b);
a = dr[0];
}
}
b = b.add(TWO);
}
result.add(b); //b will always be prime here...
}
return result;
}
public static boolean isSemi(BigInteger x){
List<BigInteger> decomp = primeDecomp(x);
return decomp != null && decomp.size() == 2;
}
public static void main(String[] args){
for(int i = 2; i <= 100; i++){
if(isSemi(BigInteger.valueOf(i))){
System.out.print(i + " ");
}
}
System.out.println();
for(int i = 1675; i <= 1680; i++){
if(isSemi(BigInteger.valueOf(i))){
System.out.print(i + " ");
}
}
}
}
- Output:
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 1678 1679
Works with gojq, the Go implementation of jq
def is_semiprime:
{i: 2, n: ., nf: 0}
| until( .i > .n or .result;
until(.n % .i != 0 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;Examples
(1679, 1680) | "\(.) => \(is_semiprime)"- Output:
1679 => true 1680 => false
using Primes
issemiprime(n::Integer) = sum(values(factor(n))) == 2
@show filter(issemiprime, 1:100)
- Output:
filter(issemiprime, 1: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]
// version 1.1.2
fun isSemiPrime(n: Int): Boolean {
var nf = 0
var nn = n
for (i in 2..nn)
while (nn % i == 0) {
if (nf == 2) return false
nf++
nn /= i
}
return nf == 2
}
fun main(args: Array<String>) {
for (v in 1675..1680)
println("$v ${if (isSemiPrime(v)) "is" else "isn't"} semi-prime")
}
- Output:
1675 isn't semi-prime 1676 isn't semi-prime 1677 isn't semi-prime 1678 is semi-prime 1679 is semi-prime 1680 isn't semi-prime
#!/bin/ksh
# Semiprime - As translated from C
# # Variables:
#
# # Functions:
#
# Function _issemiprime(p2) - return 1 if p2 semiprime, 0 if not
#
function _issemiprime {
typeset _p2 ; integer _p2=$1
typeset _p _f ; integer _p _f=0
for ((_p=2; (_f<2 && _p*_p<=_p2); _p++)); do
while (( _p2 % _p == 0 )); do
(( _p2 /= _p ))
(( _f++ ))
done
done
return $(( _f + (_p2 > 1) == 2 ))
}
######
# main #
######
integer i
for ((i=2; i<100; i++)); do
_issemiprime ${i}
(( $? )) && printf " %d" ${i}
done
echo
- Output:
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
{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
on isSemiPrime (n)
div = 2
cnt = 0
repeat while cnt < 3 and n <> 1
if n mod div = 0 then
n = n / div
cnt = cnt + 1
else
div = div + 1
end if
end repeat
return cnt=2
endres = []
repeat with i = 1 to 100
if isSemiPrime(i) then res.add(i)
end repeat
put res- Output:
-- [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]
function semiprime (n)
local divisor, count = 2, 0
while count < 3 and n ~= 1 do
if n % divisor == 0 then
n = n / divisor
count = count + 1
else
divisor = divisor + 1
end
end
return count == 2
end
for n = 1675, 1680 do
print(n, semiprime(n))
end
- Output:
1675 false 1676 false 1677 false 1678 true 1679 true 1680 false
SemiPrimes := proc( n )
local fact;
fact := NumberTheory:-Divisors( n ) minus {1, n};
if numelems( fact ) in {1,2} and not( member( 'false', isprime ~ ( fact ) ) ) then
return n;
else
return NULL;
end if;
end proc:
{ seq( SemiPrimes( i ), i = 1..100 ) };
Output:
{ 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 }
semiPrimeQ[n_Integer] := Module[{factors, numfactors},
factors = FactorInteger[n] // Transpose;
numfactors = factors[[2]] // Total ;
numfactors == 2
]
Example use: find all semiprimes less than 100:
semiPrimeQ[#] & /@ Range[100];
Position[%, True] // Flatten
- Output:
{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}
/* 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);
- Output:
[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]
isSemiprime = function(num)
divisor = 2
primes = 0
while primes < 3 and num != 1
if num % divisor == 0 then
num = num / divisor;
primes = primes + 1
else
divisor = divisor + 1
end if
end while
return primes == 2
end function
print "Semiprimes up to 100:"
results = []
for i in range(2, 100)
if isSemiprime(i) then results.push i
end for
print results
- Output:
Semiprimes up to 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]
MODULE Semiprime;
FROM STextIO IMPORT
SkipLine, WriteLn, WriteString;
FROM SWholeIO IMPORT
ReadInt;
VAR
N: INTEGER;
PROCEDURE FactorsCnt(N: INTEGER): CARDINAL;
VAR
Count, F, AN: CARDINAL;
BEGIN
AN := ABS(N);
Count := 0;
IF AN >= 2 THEN
FOR F := 2 TO AN DO
WHILE AN MOD F = 0 DO
Count := Count + 1;
AN := AN DIV F
END
END
END;
RETURN Count
END FactorsCnt;
BEGIN
WriteString("Enter an integer: ");
ReadInt(N);
SkipLine;
IF FactorsCnt(N) = 2 THEN
WriteString("It is a semiprime.")
ELSE
WriteString("It is not a semiprime.")
END;
WriteLn;
END Semiprime.
- Output:
(2 samples)
Enter an integer: 33 It is a semiprime.
Enter an integer: 60 It is not a semiprime.
;;; Practically identical to the EchoLisp solution
(define (semiprime? n)
(= (length (factor n)) 2))
;
;;; Example (sadly factor doesn't accept bigints)
(println (filter semiprime? (sequence 2 100)))
(setq x 9223372036854775807)
(while (not (semiprime? x)) (-- x))
(println "Biggest semiprime reachable: " x " = " ((factor x) 0) " x " ((factor x) 1))
- Output:
(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) Biggest semiprime reachable: 9223372036854775797 = 3 x 3074457345618258599
proc isSemiPrime(k: int): bool =
var
i = 2
count = 0
x = k
while i <= x and count < 3:
if x mod i == 0:
x = x div i
inc count
else:
inc i
result = count == 2
for k in 1675..1680:
echo k, (if k.isSemiPrime(): " is" else: " isn’t"), " semi-prime"
- Output:
1675 isn't semi-prime 1676 isn't semi-prime 1677 isn't semi-prime 1678 is semi-prime 1679 is semi-prime 1680 isn't semi-prime
MODULE SemiPrimes;
IMPORT Math, Out;
(* returns TRUE if n is semi-prime, FALSE otherwise *)
(* n is semi prime if it has exactly two prime factors *)
PROCEDURE isSemiPrime( n : INTEGER ) : BOOLEAN;
VAR factor, factorCount, maxLowFactor, otherFactor : INTEGER;
BEGIN
(* We only need to consider factors between 2 and *)
(* sqrt( n ) inclusive. If there is only one of these *)
(* then it must be a prime factor and so the number *)
(* is semi prime *)
factorCount := 0;
maxLowFactor := FLOOR( Math.sqrt( FLT( ABS( n ) ) ) );
factor := 2;
WHILE ( factor <= maxLowFactor ) & ( factorCount < 2 ) DO
IF n MOD factor = 0 THEN
INC( factorCount );
(* check the factor isn't a repeated factor *)
IF n # factor * factor THEN
(* the factor isn't the square root *)
otherFactor := n DIV factor;
IF otherFactor MOD factor = 0 THEN
(* have a repeated factor *)
INC( factorCount )
END
END
END;
INC( factor );
END
RETURN factorCount = 1
END isSemiPrime;
PROCEDURE showSemiPrimes( title : ARRAY OF CHAR; fromN, toN : INTEGER );
VAR i : INTEGER;
BEGIN
Out.String( title );Out.String( ":" );Out.Ln;Out.String( " " );
FOR i := fromN TO toN DO
IF isSemiPrime( i ) THEN Out.String( " " );Out.Int( i, 0 ) END
END;
Out.Ln
END showSemiPrimes;
BEGIN
showSemiPrimes( "semi primes below 100", 1, 99 );
showSemiPrimes( "semi primes between 1670 and 1690", 1670, 1690 )
END SemiPrimes.
- Output:
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 between 1670 and 1690:
1671 1673 1678 1679 1681 1685 1687 1689
class SemiPrime {
function : Main(args : String[]) ~ Nil {
for(i := 0; i < 100; i+=1;) {
if(SemiPrime(i)) {
"{$i} "->Print();
};
};
IO.Console->PrintLine();
}
function : native : SemiPrime(n : Int) ~ Bool {
nf := 0;
for(i := 2; i <= n; i+=1;) {
while(n%i = 0) {
if(nf = 2) {
return false;
};
nf+=1;
n /= i;
};
};
return nf = 2;
}
}Output:
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
func: semiprime(n)
| i |
0 2 n sqrt asInteger for: i [ while(n i /mod swap 0 &=) [ ->n 1+ ] drop ]
n 1 > ifTrue: [ 1+ ] 2 == ;- Output:
100 seq filter(#semiprime) println [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]
issemi(n)=bigomega(n)==2A faster version might use trial division and primality testing:
issemi(n)={
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 factorint), so this version is in PARI:
long
issemiprime(GEN n)
{
if (typ(n) != t_INT)
pari_err_TYPE("issemiprime", n);
if (signe(n) <= 0)
return 0;
ulong nn = itou_or_0(n);
if (nn)
return uissemiprime(nn);
pari_sp ltop = avma;
if (!mpodd(n)) {
long ret = mod4(n) && isprime(shifti(n, -1));
avma = ltop;
return ret;
}
long p;
forprime_t primepointer;
u_forprime_init(&primepointer, 3, 997);
while ((p = u_forprime_next(&primepointer))) {
if (dvdis(n, p)) {
long ret = isprime(diviuexact(n, p));
avma = ltop;
return ret;
}
}
if (isprime(n))
return 0;
if (DEBUGLEVEL > 3)
pari_printf("issemi: Number is a composite with no small prime factors; using general factoring mechanisms.");
GEN fac = Z_factor_until(n, shifti(n, -1)); /* Find a nontrivial factor -- returns just the factored part */
GEN expo = gel(fac, 2);
GEN pr = gel(fac, 1);
long len = glength(expo);
if (len > 2) {
avma = ltop;
return 0;
}
if (len == 2) {
if (cmpis(gel(expo, 1), 1) > 0 || cmpis(gel(expo, 2), 1) > 0) {
avma = ltop;
return 0;
}
GEN P = gel(pr, 1);
GEN Q = gel(pr, 2);
long ret = isprime(P) && isprime(Q) && equalii(mulii(P, Q), n);
avma = ltop;
return ret;
}
if (len == 1) {
long e = itos(gel(expo, 1));
if (e == 2) {
GEN P = gel(pr, 1);
long ret = isprime(P) && equalii(sqri(P), n);
avma = ltop;
return ret;
} else if (e > 2) {
avma = ltop;
return 0;
}
GEN P = gel(pr, 1);
long ret = isprime(P) && isprime(diviiexact(n, P));
avma = ltop;
return ret;
}
pari_err_BUG(pari_sprintf("Z_factor_until returned an unexpected value %Ps at n = %Ps, exiting...", fac, n));
avma = ltop;
return 0; /* never used */
}
program SemiPrime;
{$IFDEF FPC}
{$Mode objfpc}// compiler switch to use result
{$ELSE}
{$APPTYPE CONSOLE} // for Delphi
{$ENDIF}
uses
primTrial;
function isSemiprime(n: longWord;doWrite:boolean): boolean;
var
fac1 : LongWord;
begin
//a simple isAlmostPrime(n,2) would do without output;
fac1 := SmallFactor(n);
IF fac1 < n then
Begin
n := n div fac1;
result := SmallFactor(n) = n;
if result AND doWrite then
write(fac1:10,'*',n:11)
end
else
result := false;
end;
var
i,k : longWord;
BEGIN
For i := 2 to 97 do
IF isSemiPrime(i,false) then
write(i:3);
writeln;
//test for big numbers
k := 4000*1000*1000;
i := k-100;
repeat
IF isSemiPrime(i,true) then
writeln(' = ',i:10);
inc(i);
until i> k;
END.
- output
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
71* 56338027 = 3999999917
42307* 94547 = 3999999929
59* 67796609 = 3999999931
5* 799999987 = 3999999935
2* 1999999973 = 3999999946
11* 363636359 = 3999999949
103* 38834951 = 3999999953
12007* 333139 = 3999999973
7* 571428569 = 3999999983
5* 799999999 = 3999999995
With late versions of the ntheory module, we can use is_semiprime to get answers for 64-bit numbers in single microseconds.
use ntheory "is_semiprime";
for ([1..100], [1675..1681], [2,4,99,100,1679,5030,32768,1234567,9876543,900660121]) {
print join(" ",grep { is_semiprime($_) } @$_),"\n";
}
- Output:
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 4 1679 1234567 900660121
One can also use factor in scalar context, which gives the number of factors (like bigomega in Pari/GP and PrimeOmega in Mathematica). This skips some optimizations but at these small sizes it doesn't matter.
use ntheory "factor";
print join(" ", grep { scalar factor($_) == 2 } 1..100),"\n";
While is_semiprime is the fastest way, we can do some of its pre-tests by hand, such as:
use ntheory qw/factor is_prime trial_factor/;
sub issemi {
my $n = shift;
if ((my @p = trial_factor($n,500)) > 1) {
return 0 if @p > 2;
return !!is_prime($p[1]) if @p == 2;
}
2 == factor($n);
}
function semiprime(integer n) return length(prime_factors(n,true))==2 end function pp(filter(tagset(100)&tagset(1680,1675),semiprime),{pp_IntCh,false})
- Output:
{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}
<?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");
?>
- Output:
Enter an integer: 60 It is not a semiprime.
Enter an integer: 33 It is a semiprime.
(de factor (N)
(make
(let
(D 2
L (1 2 2 . (4 2 4 2 4 6 2 6 .))
M (sqrt N) )
(while (>= M D)
(if (=0 (% N D))
(setq M
(sqrt (setq N (/ N (link D)))) )
(inc 'D (pop 'L)) ) )
(link N) ) ) )
(println
(filter
'((X)
(let L (factor X)
(and (cdr L) (not (cddr L))) ) )
(conc (range 1 100) (range 1675 1680)) ) )
(bye)- Output:
(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)
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.
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.
*process source attributes xref nest or(!);
/*--------------------------------------------------------------------
* 22.02.2014 Walter Pachl using the is_prime code from
* PL/I 'prime decomposition'
* 23.02. WP start test for second prime with 2 or first prime found
*-------------------------------------------------------------------*/
spb: Proc options(main);
Dcl a(10) Bin Fixed(31)
Init(900660121,2,4,1679,1234567,32768,99,9876543,100,5040);
Dcl (x,n,nf,i,j) Bin Fixed(31) Init(0);
Dcl f(3) Bin Fixed(31);
Dcl txt Char(30) Var;
Dcl bit Bit(1);
Do i=1 To hbound(a);
bit=is_semiprime(a(i));
Select(nf);
When(0,1) txt=' is prime';
When(2) txt=' is semiprime '!!factors(a(i));
Otherwise txt=' is NOT semiprime '!!factors(a(i));
End;
Put Edit(a(i),bit,txt)(Skip,f(10),x(1),b(1),a);
End;
is_semiprime: Proc(x) Returns(bit(1));
/*--------------------------------------------------------------------
* Returns '1'b if x is semiprime, '0'b otherwise
* in addition
* it sets f(1) and f(2) to the first (or only) prime factor(s)
*-------------------------------------------------------------------*/
Dcl x Bin Fixed(31);
nf=0;
f=0;
x=a(i);
n=x;
f(1)=2;
loop:
Do While(nf<=2 & n>1);
If is_prime(n) Then Do;
Call mem(n);
Leave loop;
End;
Else Do;
loop2:
Do j=f(1) By 1 While(j*j<=n);
If is_prime(j)&mod(n,j)=0 Then Do;
Call mem(j);
n=n/j;
Leave loop2;
End;
End;
End;
End;
Return(nf=2);
End;
is_prime: Proc(n) Returns(bit(1));
Dcl n Bin Fixed(31);
Dcl i Bin Fixed(31);
If n < 2 Then Return('0'b);
If n = 2 Then Return('1'b);
If mod(n,2)=0 Then Return('0'b);
Do i = 3 by 2 While(i*i<=n);
If mod(n,i)=0 Then Return('0'b);
End;
Return('1'b);
End is_prime;
mem: Proc(x);
Dcl x Bin Fixed(31);
nf+=1;
f(nf)=x;
End;
factors: Proc(x) Returns(Char(150) Var);
Dcl x Bin Fixed(31);
Dcl (res,net) Char(150) Var Init('');
Dcl (i,f3) Bin Fixed(31);
res=f(1)!!'*'!!f(2);
f3=x/(f(1)*f(2));
If f3>1 Then
res=res!!'*'!!f3;
Do i=1 To length(res);
If substr(res,i,1)>' ' Then
net=net!!substr(res,i,1);
End;
Return(net);
End;
End spb;Output:
900660121 1 is semiprime 30011*30011
2 0 is prime
4 1 is semiprime 2*2
1679 1 is semiprime 23*73
1234567 1 is semiprime 127*9721
32768 0 is NOT semiprime 2*2*8192
99 0 is NOT semiprime 3*3*11
9876543 0 is NOT semiprime 3*227*14503
100 0 is NOT semiprime 2*2*25
5040 0 is NOT semiprime 2*2*1260
... under CP/M (or an emulator)
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- Output:
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
local function semiprime(n)
if n < 3 then return false end
local nf = 0
for i = 2, n do
while n % i == 0 do
if nf == 2 then return false end
nf += 1
n //= i
end
end
return nf == 2
end
for v = 1675, 1680 do
print($"{v} -> {semiprime(v) ? "is" : "isn't"} semi-prime")
end
- Output:
1675 -> isn't semi-prime 1676 -> isn't semi-prime 1677 -> isn't semi-prime 1678 -> is semi-prime 1679 -> is semi-prime 1680 -> isn't semi-prime
function isPrime ($n) {
if ($n -le 1) {$false}
elseif (($n -eq 2) -or ($n -eq 3)) {$true}
else{
$m = [Math]::Floor([Math]::Sqrt($n))
(@(2..$m | where {($_ -lt $n) -and ($n % $_ -eq 0) }).Count -eq 0)
}
}
function semiprime ($n) {
if($n -gt 3) {
$lim = [Math]::Floor($n/2)+1
$i = 2
while(($i -lt $lim) -and ($n%$i -ne 0)){ $i += 1}
if($i -eq $lim){@()}
elseif(-not (isPrime ($n/$i))){@()}
else{@($i,($n/$i))}
} else {@()}
}
$OFS = " x "
"1679: $(semiprime 1679)"
"87: $(semiprime 87)"
"25: $(semiprime 25)"
"12: $(semiprime 12)"
"6: $(semiprime 6)"
$OFS = " "
"semiprime from 1 to 100: $(1..100 | where {semiprime $_})"
Output:
1679: 23 x 73 87: 3 x 29 25: 5 x 5 12: 6: 2 x 3 semiprime from 1 to 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
works with swi-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).
- Output:
?- 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.
;;; 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- Output:
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
This imports Prime decomposition#Python
from prime_decomposition import decompose
def semiprime(n):
d = decompose(n)
try:
return next(d) * next(d) == n
except StopIteration:
return False
- Output:
From Idle:
>>> semiprime(1679)
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]
>>>
primefactors is defined at Prime decomposition.
[ primefactors size 2 = ] is semiprime ( n --> b )
say "Semiprimes less than 100:" cr
100 times [ i^ semiprime if [ i^ echo sp ] ]- Output:
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
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.
#lang racket
(require math)
(define (pair-factorize n)
"Return all two-number factorizations of a number"
(let ([up-limit (integer-sqrt n)])
(map (λ (x) (list x (/ n x)))
(filter (λ (x) (<= x up-limit)) (divisors n)))))
(define (semiprime n)
"Determine if a number is semiprime i.e. a product of two primes.
Check if any pair of complete factors consists of primes."
(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).
#lang racket
(require math)
(define (semiprime n)
"Alternative implementation.
Check if there are two prime factors whose product is the argument
or if there is a single prime factor whose square is the argument"
(let ([prime-factors (factorize n)])
(or (and (= (length prime-factors) 1)
(= (expt (caar prime-factors) (cadar prime-factors)) n))
(and (= (length prime-factors) 2)
(= (foldl (λ (x y) (* (car x) y)) 1 prime-factors) n)))))
(formerly Perl 6) Here is a naive, grossly inefficient implementation.
sub is-semiprime (Int $n --> Bool) {
not $n.is-prime and
.is-prime given
$n div first $n %% *, flat grep &is-prime, 2 .. *;
}
use Test;
my @primes = flat grep &is-prime, 2 .. 100;
for ^5 {
nok is-semiprime([*] my @f1 = @primes.roll(1)), ~@f1;
ok is-semiprime([*] my @f2 = @primes.roll(2)), ~@f2;
nok is-semiprime([*] my @f3 = @primes.roll(3)), ~@f3;
nok is-semiprime([*] my @f4 = @primes.roll(4)), ~@f4;
}
- Output:
ok 1 - 17 ok 2 - 47 23 ok 3 - 23 37 41 ok 4 - 53 37 67 47 ok 5 - 5 ok 6 - 73 43 ok 7 - 13 53 71 ok 8 - 7 79 37 71 ok 9 - 41 ok 10 - 71 37 ok 11 - 37 53 43 ok 12 - 3 2 47 67 ok 13 - 17 ok 14 - 41 61 ok 15 - 71 31 79 ok 16 - 97 17 73 17 ok 17 - 61 ok 18 - 73 47 ok 19 - 13 19 5 ok 20 - 37 97 11 31
More efficient example
Here is a more verbose, but MUCH more efficient implementation. Demonstrating using it to find an infinite list of semiprimes and to check a range of integers to find the semiprimes.
sub is-semiprime ( Int $n where * > 0 ) {
return False if $n.is-prime;
my $factor = find-factor( $n );
return True if $factor.is-prime && ( $n div $factor ).is-prime;
False;
}
sub find-factor ( Int $n, $constant = 1 ) {
my $x = 2;
my $rho = 1;
my $factor = 1;
while $factor == 1 {
$rho *= 2;
my $fixed = $x;
for ^$rho {
$x = ( $x * $x + $constant ) % $n;
$factor = ( $x - $fixed ) gcd $n;
last if 1 < $factor;
}
}
$factor = find-factor( $n, $constant + 1 ) if $n == $factor;
$factor;
}
INIT my $start = now;
# Infinite list of semiprimes
constant @semiprimes = lazy gather for 4 .. * { .take if .&is-semiprime };
# Show the semiprimes < 100
say 'Semiprimes less than 100:';
say @semiprimes[^ @semiprimes.first: * > 100, :k ], "\n";
# Check individual integers, or in this case, a range
my $s = 2⁹⁷ - 1;
say "Is $_ semiprime?: ", .&is-semiprime for $s .. $s + 30;
say 'elapsed seconds: ', now - $start;
- Output:
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) Is 158456325028528675187087900671 semiprime?: True Is 158456325028528675187087900672 semiprime?: False Is 158456325028528675187087900673 semiprime?: False Is 158456325028528675187087900674 semiprime?: False Is 158456325028528675187087900675 semiprime?: False Is 158456325028528675187087900676 semiprime?: False Is 158456325028528675187087900677 semiprime?: False Is 158456325028528675187087900678 semiprime?: False Is 158456325028528675187087900679 semiprime?: False Is 158456325028528675187087900680 semiprime?: False Is 158456325028528675187087900681 semiprime?: False Is 158456325028528675187087900682 semiprime?: False Is 158456325028528675187087900683 semiprime?: False Is 158456325028528675187087900684 semiprime?: False Is 158456325028528675187087900685 semiprime?: False Is 158456325028528675187087900686 semiprime?: False Is 158456325028528675187087900687 semiprime?: False Is 158456325028528675187087900688 semiprime?: False Is 158456325028528675187087900689 semiprime?: False Is 158456325028528675187087900690 semiprime?: False Is 158456325028528675187087900691 semiprime?: False Is 158456325028528675187087900692 semiprime?: False Is 158456325028528675187087900693 semiprime?: False Is 158456325028528675187087900694 semiprime?: False Is 158456325028528675187087900695 semiprime?: False Is 158456325028528675187087900696 semiprime?: False Is 158456325028528675187087900697 semiprime?: False Is 158456325028528675187087900698 semiprime?: False Is 158456325028528675187087900699 semiprime?: False Is 158456325028528675187087900700 semiprime?: False Is 158456325028528675187087900701 semiprime?: True elapsed seconds: 0.0574433
version 1
/* REXX ---------------------------------------------------------------
* 20.02.2014 Walter Pachl relying on 'prime decomposition'
* 21.02.2014 WP Clarification: I copied the algorithm created by
* Gerard Schildberger under the task referred to above
* 21.02.2014 WP Make sure that factr is not called illegally
*--------------------------------------------------------------------*/
Call test 4
Call test 9
Call test 10
Call test 12
Call test 1679
Exit
test:
Parse Arg z
If is_semiprime(z) Then Say z 'is semiprime' fl
Else Say z 'is NOT semiprime' fl
Return
is_semiprime:
Parse Arg z
If z<1 | datatype(z,'W')=0 Then Do
Say 'Argument ('z') must be a natural number (1, 2, 3, ...)'
fl=''
End
Else
fl=factr(z)
Return words(fl)=2
/*----------------------------------FACTR subroutine-----------------*/
factr: procedure; parse arg x 1 z,list /*sets X&Z to arg1, LIST=''. */
if x==1 then return '' /*handle the special case of X=1.*/
j=2; call .factr /*factor for the only even prime.*/
j=3; call .factr /*factor for the 1st odd prime.*/
j=5; call .factr /*factor for the 2nd odd prime.*/
j=7; call .factr /*factor for the 3rd odd prime.*/
j=11; call .factr /*factor for the 4th odd prime.*/
j=13; call .factr /*factor for the 5th odd prime.*/
j=17; call .factr /*factor for the 6th odd prime.*/
/* [?] could be optimized more.*/
/* [?] J in loop starts at 17+2*/
do y=0 by 2; j=j+2+y//4 /*insure J isn't divisible by 3. */
if right(j,1)==5 then iterate /*fast check for divisible by 5. */
if j*j>z then leave /*are we higher than the v of Z ?*/
if j>Z then leave /*are we higher than value of Z ?*/
call .factr /*invoke .FACTR for some factors.*/
end /*y*/ /* [?] only tests up to the v X.*/
/* [?] LIST has a leading blank.*/
if z==1 then return list /*if residual=unity, don't append*/
return list z /*return list, append residual. */
/*-------------------------------.FACTR internal subroutine----------*/
.factr: do while z//j==0 /*keep dividing until we can't. */
list=list j /*add number to the list (J). */
z=z%j /*% (percent) is integer divide.*/
end /*while z··· */ /* // ?---remainder integer ÷.*/
return /*finished, now return to invoker*/
Output
4 is semiprime 2 2 9 is semiprime 3 3 10 is semiprime 2 5 12 is NOT semiprime 2 2 3 1679 is semiprime 23 73
Version 2
Modules: How to use
Modules: Source code
Below version relies on function Semiprime(x) in Numbers, and that function uses Miller-Rabin Prime(x) in Numbers. This means you can process pretty big numbers, but the performance is difficult to predict.
-- 24 Aug 2025
include Setting
say 'SEMIPRIME'
say version
say
numeric digits 100
call Sequence 1,200
call Sequence 100001,100200
call Sequence 1000000001,1000000200
call Sequence 158456325028528675187087900601,158456325028528675187087900660
exit
Sequence:
arg xx,yy
say 'Semiprimes between' xx 'to' yy
if yy = '' then
yy = xx
l = length(yy)+1
n = 0
do i = xx to yy
if Semiprime(i) then do
n = n+1
call Charout ,right(i,l)
if n//5 = 0 then
say
end
end
say
say Format(Time('e'),,3) 'seconds'
say
return
include Math
- Output:
SEMIPRIME - 4 Mar 2025 REXX-Regina_3.9.6(MT) 5.00 29 Apr 2024 Semiprimes between 1 to 200 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 106 111 115 118 119 121 122 123 129 133 134 141 142 143 145 146 155 158 159 161 166 169 177 178 183 185 187 194 0.001 seconds Semiprimes between 100001 to 100200 100001 100007 100013 100021 100027 100029 100031 100033 100039 100041 100042 100046 100047 100051 100055 100059 100063 100066 100077 100081 100087 100091 100094 100097 100099 100102 100105 100106 100115 100117 100121 100123 100127 100131 100133 100138 100139 100141 100145 100154 100157 100159 100171 100173 100174 100186 100187 100199 0.007 seconds Semiprimes between 1000000001 to 1000000200 1000000006 1000000013 1000000018 1000000019 1000000031 1000000047 1000000051 1000000057 1000000061 1000000069 1000000081 1000000082 1000000083 1000000099 1000000101 1000000109 1000000111 1000000114 1000000121 1000000129 1000000137 1000000138 1000000142 1000000151 1000000154 1000000163 1000000165 1000000169 1000000178 1000000186 1000000187 1000000189 1000000193 1000000195 1000000198 1000000199 0.142 seconds Semiprimes between 158456325028528675187087900601 to 158456325028528675187087900660 158456325028528675187087900638 158456325028528675187087900641 158456325028528675187087900647 158456325028528675187087900659 1.443 seconds
prime = 1679
decomp(prime)
func decomp nr
x = ""
sum = 0
for i = 1 to nr
if isPrime(i) and nr % i = 0
sum = sum + 1
x = x + string(i) + " * " ok
if i = nr and sum = 2
x2 = substr(x,1,(len(x)-2))
see string(nr) + " = " + x2 + "is semiprime" + nl
but i = nr and sum != 2 see string(nr) + " is not semiprime" + nl ok
next
func isPrime n
if n < 2 return false ok
if n < 4 return true ok
if n % 2 = 0 and n != 2 return false ok
for d = 3 to sqrt(n) step 2
if n % d = 0 return false ok
next
return truePDIV is defined at Prime decomposition
≪ PDIV SIZE 2 == ≫ 'SPR1?' STO ≪ { } 1 100 FOR n IF n SPR1? THEN n + END NEXT ≫ EVAL
- Output:
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 }
require 'prime'
# 75.prime_division # Returns the factorization.75 divides by 3 once and by 5 twice => [[3, 1], [5, 2]]
class Integer
def semi_prime?
prime_division.sum(&:last) == 2
end
end
p 1679.semi_prime? # true
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]
Faster version using 'factor' function from [U|Li]nux Core Utilities library.
def semiprime(n)
`factor #{n}`.split.size == 3
end
n = 2**72 - 1 #4722366482869645213695
(n-50..n).each { |n| puts "#{n} -> #{semiprime(n)}" }
- Output:
4722366482869645213645 -> false 4722366482869645213646 -> false 4722366482869645213647 -> false 4722366482869645213648 -> false 4722366482869645213649 -> false 4722366482869645213650 -> false 4722366482869645213651 -> true 4722366482869645213652 -> false 4722366482869645213653 -> false 4722366482869645213654 -> false 4722366482869645213655 -> false 4722366482869645213656 -> false 4722366482869645213657 -> false 4722366482869645213658 -> false 4722366482869645213659 -> false 4722366482869645213660 -> false 4722366482869645213661 -> false 4722366482869645213662 -> false 4722366482869645213663 -> true 4722366482869645213664 -> false 4722366482869645213665 -> false 4722366482869645213666 -> false 4722366482869645213667 -> false 4722366482869645213668 -> false 4722366482869645213669 -> false 4722366482869645213670 -> false 4722366482869645213671 -> false 4722366482869645213672 -> false 4722366482869645213673 -> true 4722366482869645213674 -> false 4722366482869645213675 -> false 4722366482869645213676 -> false 4722366482869645213677 -> false 4722366482869645213678 -> false 4722366482869645213679 -> false 4722366482869645213680 -> false 4722366482869645213681 -> false 4722366482869645213682 -> false 4722366482869645213683 -> false 4722366482869645213684 -> false 4722366482869645213685 -> false 4722366482869645213686 -> false 4722366482869645213687 -> false 4722366482869645213688 -> false 4722366482869645213689 -> true 4722366482869645213690 -> false 4722366482869645213691 -> false 4722366482869645213692 -> false 4722366482869645213693 -> false 4722366482869645213694 -> false 4722366482869645213695 -> false
extern crate primal;
fn isqrt(n: usize) -> usize {
(n as f64).sqrt() as usize
}
fn is_semiprime(mut n: usize) -> bool {
let root = isqrt(n) + 1;
let primes1 = primal::Sieve::new(root);
let mut count = 0;
for i in primes1.primes_from(2).take_while(|&x| x < root) {
while n % i == 0 {
n /= i;
count += 1;
}
if n == 1 {
break;
}
}
if n != 1 {
count += 1;
}
count == 2
}
#[test]
fn test1() {
assert_eq!((2..10).filter(|&n| is_semiprime(n)).count(), 3);
}
#[test]
fn test2() {
assert_eq!((2..100).filter(|&n| is_semiprime(n)).count(), 34);
}
#[test]
fn test3() {
assert_eq!((2..1_000).filter(|&n| is_semiprime(n)).count(), 299);
}
#[test]
fn test4() {
assert_eq!((2..10_000).filter(|&n| is_semiprime(n)).count(), 2_625);
}
#[test]
fn test5() {
assert_eq!((2..100_000).filter(|&n| is_semiprime(n)).count(), 23_378);
}
#[test]
fn test6() {
assert_eq!((2..1_000_000).filter(|&n| is_semiprime(n)).count(), 210_035);
}
functional version of is_semiprime:
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
}
- Output:
running 6 tests test test1 ... ok test test2 ... ok test test3 ... ok test test4 ... ok test test5 ... ok test test6 ... ok test result: ok. 6 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out
object Semiprime extends App {
def isSP(n: Int): Boolean = {
var nf: Int = 0
var l = n
for (i <- 2 to l/2) {
while (l % i == 0) {
if (nf == 2) return false
nf +=1
l /= i
}
}
nf == 2
}
(2 to 100) filter {isSP(_) == true} foreach {i => print("%d ".format(i))}
println
1675 to 1681 foreach {i => println(i+" -> "+isSP(i))}
}
- Output:
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 1675 -> false 1676 -> false 1677 -> false 1678 -> true 1679 -> true 1680 -> false 1681 -> true
$ include "seed7_05.s7i";
const func boolean: semiPrime (in var integer: n) is func
result
var boolean: isSemiPrime is TRUE;
local
var integer: p is 2;
var integer: f is 0;
begin
while f < 2 and p**2 <= n do
while n rem p = 0 do
n := n div p;
incr(f);
end while;
incr(p);
end while;
isSemiPrime := f + ord(n > 1) = 2;
end func;
const proc: main is func
local
var integer: v is 0;
begin
for v range 1675 to 1680 do
writeln(v <& " -> " <& semiPrime(v));
end for;
end func;- Output:
1675 -> FALSE 1676 -> FALSE 1677 -> FALSE 1678 -> TRUE 1679 -> TRUE 1680 -> FALSE
Built-in:
say is_semiprime(2**128 + 1) #=> true
say is_semiprime(2**256 - 1) #=> false
User-defined function, with trial division up to a given bound B:
func is_semiprime(n, B=1e4) {
with (n.trial_factor(B)) { |f|
return false if (f.len > 2)
return f.all { .is_prime } if (f.len == 2)
}
n.factor.len == 2
}
say [2,4,99,100,1679,32768,1234567,9876543,900660121].grep(is_semiprime)
- Output:
[4, 1679, 1234567, 900660121]
import Foundation
func primes(n: Int) -> AnyGenerator<Int> {
var (seive, i) = ([Int](0..<n), 1)
let lim = Int(sqrt(Double(n)))
return anyGenerator {
while ++i < n {
if seive[i] != 0 {
if i <= lim {
for notPrime in stride(from: i*i, to: n, by: i) {
seive[notPrime] = 0
}
}
return i
}
}
return nil
}
}
func isSemiPrime(n: Int) -> Bool {
let g = primes(n)
while let first = g.next() {
if n % first == 0 {
if first * first == n {
return true
} else {
while let second = g.next() {
if first * second == n { return true }
}
}
}
}
return false
}
package require math::numtheory
proc isSemiprime n {
if {!($n & 1)} {
return [::math::numtheory::isprime [expr {$n >> 1}]]
}
for {set i 3} {$i*$i < $n} {incr i 2} {
if {$n / $i * $i != $n && [::math::numtheory::isprime $i]} {
if {[::math::numtheory::isprime [expr {$n/$i}]]} {
return 1
}
}
}
return 0
}
for {set n 1675} {$n <= 1680} {incr n} {
puts -nonewline "$n is ... "
if {[isSemiprime $n]} {
puts "a semiprime"
} else {
puts "NOT a semiprime"
}
}
- Output:
1675 is ... a semiprime 1676 is ... NOT a semiprime 1677 is ... a semiprime 1678 is ... a semiprime 1679 is ... a semiprime 1680 is ... NOT a semiprime
// 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();
});
- Output:
Enter an integer: 33 It is a semiprime.
Enter an integer: 60 It is not a semiprime.
var semiprime = Fn.new { |n|
if (n < 3) return false
var nf = 0
for (i in 2..n) {
while (n%i == 0) {
if (nf == 2) return false
nf = nf + 1
n = (n/i).floor
}
}
return nf == 2
}
for (v in 1675..1680) {
System.print("%(v) -> %(semiprime.call(v) ? "is" : "is not") semi-prime")
}
- Output:
1675 -> isn't semi-prime 1676 -> isn't semi-prime 1677 -> isn't semi-prime 1678 -> is semi-prime 1679 -> is semi-prime 1680 -> isn't semi-prime
func Semiprime(N); \Return 'true' if N is semiprime
int N, F, C;
[C:= 0; F:= 2;
repeat if rem(N/F) = 0 then
[C:= C+1;
N:= N/F;
]
else F:= F+1;
until F > N;
return C = 2;
];
int N;
[for N:= 1 to 100 do
if Semiprime(N) then
[IntOut(0, N); ChOut(0, ^ )];
]- Output:
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
fcn semiprime(n){
reg f = 0;
p:=2; while(f < 2 and p*p <= n){
while(0 == n % p){ n /= p; f+=1; }
p+=1;
}
return(f + (n > 1) == 2);
}- Output:
[1675 .. 1681].filter(semiprime).println(); L(1678,1679,1681)
Categories:
- Programming Tasks
- Prime Numbers
- 11l
- 360 Assembly
- Action!
- Ada
- ALGOL 60
- ALGOL 68
- ALGOL-M
- ALGOL W
- Arturo
- AutoHotkey
- AWK
- BASIC
- ANSI BASIC
- ASIC
- BASIC256
- Chipmunk Basic
- FreeBASIC
- GW-BASIC
- Minimal BASIC
- MoonRock
- Palo Alto Tiny BASIC
- PureBasic
- QuickBASIC
- Run BASIC
- Tiny BASIC
- True BASIC
- Yabasic
- Bracmat
- C
- C sharp
- C++
- Clojure
- Common Lisp
- Crystal
- D
- DCL
- Delphi
- SysUtils,StdCtrls
- EasyLang
- EchoLisp
- Elixir
- Erlang
- ERRE
- Euler
- F Sharp
- Factor
- Forth
- Frink
- FutureBasic
- Go
- Haskell
- Data.Numbers.Primes
- Hobbes
- Icon
- Unicon
- J
- Java
- Jq
- Julia
- Kotlin
- Ksh
- Lambdatalk
- Lingo
- Lua
- Maple
- Mathematica
- Wolfram Language
- Maxima
- MiniScript
- Modula-2
- NewLisp
- Nim
- Oberon-07
- Objeck
- Oforth
- PARI/GP
- Pascal
- PrimTrial
- Perl
- Ntheory
- Phix
- PHP
- PicoLisp
- PL/0
- PL/I
- PL/M
- Pluto
- PowerShell
- Prolog
- PROMAL
- Python
- Quackery
- Racket
- Raku
- REXX
- Ring
- RPL
- Ruby
- Rust
- Scala
- Seed7
- Sidef
- Swift
- Tcl
- Tcllib
- TypeScript
- Wren
- XPL0
- Zkl