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. Example: 1679 = 23 × 73 (This particular number was chosen as the length of the Arecibo message).
Write a function determining whether a given number is semiprime.
Ada
This imports the package Prime_Numbers from Prime decomposition#Ada.
<lang 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;</lang>
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.
AutoHotkey
<lang AutoHotkey>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</lang>
- 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
C
<lang c>#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; }</lang>
- 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
D
<lang d>bool semiprime(long n) pure nothrow {
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);
}</lang>
- Output:
1675 -> false 1676 -> false 1677 -> false 1678 -> true 1679 -> true 1680 -> false
Forth
<lang forth>: 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 ;</lang>
- 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
Go
<lang go>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))
}
}</lang>
- Output:
1675 -> false 1676 -> false 1677 -> false 1678 -> true 1679 -> true 1680 -> false
Haskell
<lang Haskell>isSemiprime :: Int -> Bool isSemiprime n = (length factors) == 2 && (product factors) == n ||
(length factors) == 1 && (head factors) ^ 2 == n
where factors = primeFactors n</lang>
Alternative (and faster) implementation using pattern matching: <lang Haskell>isSemiprime :: Int -> Bool isSemiprime n = case (primeFactors n) of
[f1, f2] -> f1 * f2 == n
otherwise -> False</lang>
J
Implementation:
<lang J>isSemiPrime=: 2 = #@q: ::0:"0</lang>
Example use: find all semiprimes less than 100:
<lang J> I. isSemiPrime i.100 4 6 9 10 14 15 21 22 25 26 33 34 35 38 39 46 49 51 55 57 58 62 65 69 74 77 82 85 86 87 91 93 94 95</lang>
Description: factor the number and count the primes in the factorization, is it 2?
Mathematica
<lang Mathematica>semiPrimeQ[n_Integer] := Module[{factors, numfactors},
factors = FactorInteger[n] // Transpose; numfactors = factors2 // Total ; numfactors == 2 ]
</lang> Example use: find all semiprimes less than 100: <lang Mathematica>semiPrimeQ[#] & /@ Range[100]; Position[%, True] // Flatten</lang>
- 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}
PARI/GP
<lang parigp>issemi(n)=bigomega(n)==2</lang>
A faster version might use trial division and primality testing: <lang parigp>issemi(n)={
forprime(p=2,97,if(n%p==0, return(isprime(n/p)))); if(isprime(n), return(0)); bigomega(n)==2
};</lang>
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:
<lang c>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 */
}</lang>
Perl 6
Here is a naive, grossly inefficient implementation. <lang perl6>sub is-semiprime (Int $n --> Bool) {
not $n.is-prime and
.is-prime given
$n div first $n %% *,
grep &is-prime, 2 .. *;
}
use Test; my @primes = grep &is-prime, 2 .. 100; for ^5 {
ok not is-semiprime([*] my @f1 = @primes.roll(1)), ~@f1; ok is-semiprime([*] my @f2 = @primes.roll(2)), ~@f2; ok not is-semiprime([*] my @f3 = @primes.roll(3)), ~@f3; ok not is-semiprime([*] my @f4 = @primes.roll(4)), ~@f4;
}</lang>
- 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
PL/I
<lang pli>*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;
</lang> 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
Python
This imports Prime decomposition#Python <lang python>from prime_decomposition import decompose
def semiprime(n):
d = decompose(n)
try:
return next(d) * next(d) == n
except:
return False</lang>
- Output:
From Idle: <lang python>>>> 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] >>> </lang>
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. <lang Racket>#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))))</lang>
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>#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)))))</lang>
REXX
version 1
<lang rexx>/* 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*/</lang> 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
The method used is to examine numbers, skipping primes. If composite (the 1st factor is prime), then check if the 2nd factor is prime. If so, the number is a semiprime. <lang rexx>/*REXX program determines if any number (or a range) is/are semiprime.*/ parse arg bot top . /*obtain #s from the command line*/ if bot== then bot=random() /*so, the user wants us to guess.*/ if top== then top=bot /*maybe define a range of numbers*/ w=max(length(bot), length(top)) /*get maximum width of numbers. */ if w>digits() then numeric digits w /*is there enough digits ? */
do n=bot to top /*show results for a range of #s.*/
if isSemiPrime(n) then say right(n,w) ' is semiprime.'
else say right(n,w) " isn't semiprime."
end /*n*/
exit /*stick a fork in it, we're done.*/ /*──────────────────────────────────ISPRIME subroutine──────────────────*/ isPrime: procedure; parse arg x; if x<2 then return 0 if wordpos(x,'2 3 5 7')\==0 then return 1 /*handle some special cases*/
do i=2 for 2; if x//i==0 then return 0; end /*i*/ /*÷ by 2 & 3*/
do j=5 by 6 until j*j>x; if x//j==0 then return 0 /*¬ a prime#*/
if x//(j+2)==0 then return 0 /*¬ a prime#*/
end /*j*/
return 1 /*X is a prime number, for sure.*/ /*──────────────────────────────────ISSEMIPRIME subroutine──────────────*/ isSemiPrime: procedure; arg x; if \datatype(x,'W') | x<4 then return 0 x=x/1 /*normalize the X number. */
do i=2 for 2; if x//i==0 then if isPrime(x%i) then return 1
else return 0
end /*i*/ /* [↑] divides by two and three.*/
do j=5 by 6; if j*j>x then return 0 /*÷ by #s. */
do k=j by 2 for 2; if x//k==0 then if isPrime(x%k) then return 1
else return 0
end /*k*/ /*see if 2nd factor is prime or ¬*/
end /*j*/ /*[↑] never ÷ by # divisible by 3*/</lang>
output when the input is: -1 106
-1 isn't semiprime. 0 isn't semiprime. 1 isn't semiprime. 2 isn't semiprime. 3 isn't semiprime. 4 is semiprime. 5 isn't semiprime. 6 is semiprime. 7 isn't semiprime. 8 isn't semiprime. 9 is semiprime. 10 is semiprime. 11 isn't semiprime. 12 isn't semiprime. 13 isn't semiprime. 14 is semiprime. 15 is semiprime. 16 isn't semiprime. 17 isn't semiprime. 18 isn't semiprime. 19 isn't semiprime. 20 isn't semiprime. 21 is semiprime. 22 is semiprime. 23 isn't semiprime. 24 isn't semiprime. 25 is semiprime. 26 is semiprime. 27 isn't semiprime. 28 isn't semiprime. 29 isn't semiprime. 30 isn't semiprime. 31 isn't semiprime. 32 isn't semiprime. 33 is semiprime. 34 is semiprime. 35 is semiprime. 36 isn't semiprime. 37 isn't semiprime. 38 is semiprime. 39 is semiprime. 40 isn't semiprime. 41 isn't semiprime. 42 isn't semiprime. 43 isn't semiprime. 44 isn't semiprime. 45 isn't semiprime. 46 is semiprime. 47 isn't semiprime. 48 isn't semiprime. 49 is semiprime. 50 isn't semiprime. 51 is semiprime. 52 isn't semiprime. 53 isn't semiprime. 54 isn't semiprime. 55 is semiprime. 56 isn't semiprime. 57 is semiprime. 58 is semiprime. 59 isn't semiprime. 60 isn't semiprime. 61 isn't semiprime. 62 is semiprime. 63 isn't semiprime. 64 isn't semiprime. 65 is semiprime. 66 isn't semiprime. 67 isn't semiprime. 68 isn't semiprime. 69 is semiprime. 70 isn't semiprime. 71 isn't semiprime. 72 isn't semiprime. 73 isn't semiprime. 74 is semiprime. 75 isn't semiprime. 76 isn't semiprime. 77 is semiprime. 78 isn't semiprime. 79 isn't semiprime. 80 isn't semiprime. 81 isn't semiprime. 82 is semiprime. 83 isn't semiprime. 84 isn't semiprime. 85 is semiprime. 86 is semiprime. 87 is semiprime. 88 isn't semiprime. 89 isn't semiprime. 90 isn't semiprime. 91 is semiprime. 92 isn't semiprime. 93 is semiprime. 94 is semiprime. 95 is semiprime. 96 isn't semiprime. 97 isn't semiprime. 98 isn't semiprime. 99 isn't semiprime. 100 isn't semiprime. 101 isn't semiprime. 102 isn't semiprime. 103 isn't semiprime. 104 isn't semiprime. 105 isn't semiprime. 106 is semiprime.
Ruby
<lang ruby>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.map( &:last ).inject( &:+ ) == 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]
</lang>
Scala
<lang Scala>object Semiprime extends App {
def isSP(n: Int): Boolean = {
var nf: Int = 0
var l = n
for (i <- 2 to l+1) {
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))}
}</lang>
- 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
Tcl
<lang tcl>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"
}
}</lang>
- 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