Is it a semiprime?

Question

Surprisingly, I don't think we have a code-golf question for determining if a number is semiprime.

A semiprime is a natural number that is the product of two (not necessarily distinct) prime numbers.

Simple enough, but a remarkably important concept.

Given a positive integer, determine if it is a semiprime. Your output can be in any form so long as it gives the same output for any truthy or falsey value. You may also assume your input is reasonably small enough that performance or overflow aren't an issue.

Test cases:

input -> output
1     -> false
2     -> false
3     -> false
4     -> true
6     -> true
8     -> false
30    -> false   (5 * 3 * 2), note it must be EXACTLY 2 (non-distinct) primes
49    -> true    (7 * 7)      still technically 2 primes
95    -> true
25195908475657893494027183240048398571429282126204032027777137836043662020707595556264018525880784406918290641249515082189298559149176184502808489120072844992687392807287776735971418347270261896375014971824691165077613379859095700097330459748808428401797429100642458691817195118746121515172654632282216869987549182422433637259085141865462043576798423387184774447920739934236584823824281198163815010674810451660377306056201619676256133844143603833904414952634432190114657544454178424020924616515723350778707749817125772467962926386356373289912154831438167899885040445364023527381951378636564391212010397122822120720357
      -> true, and go call someone, you just cracked RSA-2048

This is code-golf, so standard rules apply!

Answer 1

Brachylog, 2 bytes

Basically a port from Fatalize's answer to the Sphenic number challenge.

ḋĊ

Try it online!

How?

ḋĊ - implicitly takes input
ḋ  - prime factorisation (with duplicates included)
 Ċ - is a couple

Answer 2

Husk, 4 bytes

_{Look ma no Unicode!}

=2Lp

Try it online!

How?

=2Lp - a one input function
   p - prime factorisation (with duplicates included)
  L  - length
=2   - equals 2?

Answer 3

Mathematica, 16 bytes

PrimeOmega@#==2&

PrimeOmega counts the number of prime factors, counting multiplicity.

Answer 4

Pyth, 4 bytes

q2lP

Test suite.

---

How?

q2lPQ     - Q is implicit input.

q2        - Is equal to 2?
    lPQ   - The length of the prime factors of the input.

Answer 5

Python 3, 54 bytes

lambda n:0<sum((n%x<1)+(x**3==n)for x in range(2,n))<3

Try it online!

^{The previous verson had some rounding issues on large cube numbers (125,343,etc)}
This calculates the amount of divisors (not only primes), if it has 1 or 2 it returns True.
The only exception is when a number has more than two prime factors but only two divisors. In this case it is a perfect cube of a prime (its divisors are its cube root and its cube root squared). x**3==n will cover this case, adding one to the cube root entry pushes the sum up to a count of 3 and stops the false-positive. ^{thanks Jonathan Allan for writing with this beautiful explanation}

Answer 6

Ruby, 56 48 bytes

->x{r=c=2;0while x%r<1?(x/=r;c-=1):x>=r+=1;c==0}

Try it online!

How it works:

->x{                    # Lambda function
    r=c=2;              # Starting from r=2, c=2
    0 while             # Repeat (0 counts as a nop)
        x%r<1? (        # If x mod r == 0
            x/=r:       # Divide x by r
            c-=1        # decrease c
        ):              # else
            x>=r+=1     # increase r, terminate if r>x 
    );
    c==0                # True if we found 2 factors
}

Thanks Value Ink for the idea that saved 8 bytes.

Answer 7

Mathematica, 31 29 bytes

Tr[Last/@FactorInteger@#]==2&

Answer 8

Python 2, 67 bytes

lambda k:f(k)==2
f=lambda n,k=2:n/k and(f(n,k+1),1+f(n/k,k))[n%k<1]

Try it online!

-10 bytes thanks to @JonathanAllan!

Credit for the Prime factorization algorithm goes to Dennis (in the initial version)

Answer 9

Neim, 4 bytes

δ

Try it online!

Answer 10

Mathematica 32 bytes

Thanks to ngenesis for 1 byte saved

Tr@FactorInteger[#][[;;,2]]==2&

Answer 11

JavaScript (ES6), 47 bytes

Returns a boolean.

n=>(k=1)==(d=n=>++k<n?n%k?d(n):d(n/k--)+1:0)(n)

Demo

let f =

n=>(k=1)==(d=n=>++k<n?n%k?d(n):d(n/k--)+1:0)(n)

console.log(
  [...Array(200).keys()].filter(f).join`, `
)

Answer 12

Jelly, 5 bytes

ÆfL=2

Try it online!

Explanation

ÆfL=2  Main link
Æf     Prime factors
  L    Length
   =   Equals
    2  2

Answer 13

Actually, 4 bytes

ol2=

Try it online!

Answer 14

05AB1E, 4 bytes

Òg2Q

Try it online!

How?

Ò       prime factors list (with duplicates)
 g      length
   Q    equal to
  2     2

Answer 15

Dyalog APL, 18 bytes

⎕CY'dfns'
2=≢3pco⎕

Try it online!

How?

⎕CY'dfns' - import pco

3pco⎕ - run pco on input with left argument 3 (prime factors)

2=≢ - length = 2?

Answer 16

MATL, 5 bytes

Yfn2=

Try it online!

Explanation

• Yf - Prime factors.

• n - Length.

• 2= - Is equal to 2?

Answer 17

Python with SymPy 1.1.1,  57  44 bytes

-13 bytes thanks to alephalpha (use 1.1.1's primeomega)

from sympy import*
lambda n:primeomega(n)==2

Try it online!

Answer 18

Gaia, 4 bytes

ḍl2=

4 bytes seems to be a common length, I wonder why... :P

Try it online!

Explanation

ḍ     Prime factors
 l    Length
  2=  Equals 2?

Answer 19

R, 67 bytes

c=0;n=scan();for(p in(1:n)[-1:-2]-1)while(n%%p<1){c=c+1;n=n/p};c==2

Try it online!

Answer 20

Ruby, 35+8 = 43 bytes

Uses the -rprime flag to unlock the prime_division function.

->n{n.prime_division.sum(&:pop)==2}

Try it online!

Answer 21

Java 8, 69 61 bytes

n->{int r=1,c=2;for(;r++<n;)for(;n%r<1;n/=r)c--;return c==0;}

-8 bytes thanks to @Nevay.

Try it here.

Answer 22

Python 2, 75 65 bytes

lambda n:g(n)==2
g=lambda n,i=2:n/i and[g(n,i+1),1+g(n/i)][n%i<1]

Try it online!

All credit to xnor's answer for the original prime factorization code.

Answer 23

Japt, 6 5 bytes

k ʥ2

Test it online

---

Explanation

Does pretty much the same as most of the other answers: k gets the array of prime factors, Ê gets its length and ¥ checks for equality with 2.

Answer 24

C#, 112 Bytes

n=>{var r=Enumerable.Range(2,n);var l=r.Where(i=>r.All(x=>r.All(y=>y*x!=i)));return l.Any(x=>l.Any(y=>y*x==n));}

With formatting applied:

n =>
{
    var r = Enumerable.Range (2, n);
    var l = r.Where (i => r.All (x => r.All (y => y * x != i)));
    return l.Any (x => l.Any (y => y * x == n));
}

And as test program:

using System;
using System.Linq;


namespace S
{
    class P
    {
        static void Main ()
        {
            var f = new Func<int, bool> (
                n =>
                {
                    var r = Enumerable.Range (2, n);
                    var l = r.Where (i => r.All (x => r.All (y => y * x != i)));
                    return l.Any (x => l.Any (y => y * x == n));
                }
            );

            for (var i = 0; i < 100; i++)
                Console.WriteLine ($"{i} -> {f (i)}");
            Console.ReadLine ();
        }
    }
}

Which has the 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
50 -> False
51 -> True
52 -> False
53 -> False
54 -> False
55 -> True
56 -> False
57 -> True
58 -> True
59 -> False
60 -> False
61 -> False
62 -> True
63 -> False
64 -> False
65 -> True
66 -> False
67 -> False
68 -> False
69 -> True
70 -> False
71 -> False
72 -> False
73 -> False
74 -> True
75 -> False
76 -> False
77 -> True
78 -> False
79 -> False
80 -> False
81 -> False
82 -> True
83 -> False
84 -> False
85 -> True
86 -> True
87 -> True
88 -> False
89 -> False
90 -> False
91 -> True
92 -> False
93 -> True
94 -> True
95 -> True
96 -> False
97 -> False
98 -> False
99 -> False

Answer 25

Pari/GP, 17 bytes

n->bigomega(n)==2

Try it online!

Answer 26

Python 2, 90 bytes

def g(x,i=2):
 while x%i:i+=1
 return i
def f(n,l=0):
 while 1%n:l+=1;n/=g(n)
 return l==2

f takes an integer n greater than or equal to 1, returns boolean.

Try it online!

Test cases:

>>> f(1)
False
>>> f(2)
False
>>> f(3)
False
>>> f(4)
True
>>> f(6)
True
>>> f(8)
False
>>> f(30)
False
>>> f(49)
True
>>> f(95)
True

Answer 27

Retina, 45 bytes

.+
$*
^(11+)(\1)+$
$1;1$#2$*
A`\b(11+)\1+\b
;

Try it online! Link includes test cases. Explanation:

.+
$*

Convert to unary.

^(11+)(\1)+$
$1;1$#2$*

Try to find two factors.

A`\b(11+)\1+\b

Ensure both factors are prime.

;

Ensure two factors were found.

Answer 28

J, 6 bytes

5 bytes will work as a one-off:

   2=#q: 8
0
   2=#q: 9
1

I believe I need six when I define the function:

   semiprime =. 2=#@q:
   (,. semiprime) 1 + i. 20
 1 0
 2 0
 3 0
 4 1
 5 0
 6 1
 7 0
 8 0
 9 1
10 1
11 0
12 0
13 0
14 1
15 1
16 0
17 0
18 0
19 0
20 0

Answer 29

Pyke, 5 bytes

Pl02q

Try it here!

Answer 30

Perl 6, 43 bytes

{my \f=first $_%%*,2..$_;?f&&is-prime $_/f}

Try it online!

f is the smallest factor greater than 1 of the input argument $_, or Nil if $_ is 1. The return value of the function is true if f is true (ie, not Nil) AND the input argument divided by the factor is prime.

If $_ itself is prime, then f will be equal to $_, and $_ / f is 1, which is not prime, so the formula works in that case as well.

Answer 31

PHP, 75 bytes

<?php for($c=$t=2;$n=&$argv[1]>1;$t++)while($n%$t<1){$c--;$n/=$t;}echo+!$c;

Try it online!

This script is called from the command line with the number being tested as its parameter. It prints out a 1 if the number was a semi-prime, else a 0.

Explanation

<?php

Work through each integer, $t, from 2 up, to see if it's a factor. We need to keep going, dividing by the factors until $n (an alias for $argv[1], the first CLI parameter) reaches 1. (And as there is a 2 to hand, we take the chance to initialize the counter, $c, to 2.)

for ($c = $t = 2; $n = &$argv[1] > 1; $t++)

When we find a factor, we keep using it for as long as we can…

    while ($n % $t < 1) {

…each time deccrementing the factor counter…

        $c--;

…and recalculating our number.

        $n /= $t;
    }

When we reach the end, the counter can only be 0 if there were 2 factors. We ‘not’ the number, but this converts it to a boolean, so we use + to make it into 1 (the number was a semi-prime) or 0 (it wasn’t).

echo +!$c;

Answer 32

Braingolf, 8 bytes

pl2e1:0|

Try it online!

Answer 33

APL(NARS), 7 chars, 14 bytes

{2=≢π⍵}

test:

  f←{2=≢π⍵}
  f¨1 2 3 4 6 8 30 49 95
0 0 0 1 1 0 0 1 1