# Is it a semiprime?

Surprisingly, I don't think we have a 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 , so standard rules apply!

• @WheatWizard There's a slightly difference in that that one asks for 3 primes (not a big difference for almost all languages) and it's for distinct primes only (fairly different for some languages). I can discuss it with you in chat if you'd like to continue a more detailed discussion. Aug 7, 2017 at 18:30
• @WheatWizard You raise a good point, but similarly, we already have a bunch of many types of questions, and although, in contrast to what you express, most of them do add significant contribution to their area, this question has enough of a difference that I would believe that it warrants a separate question/post. Aug 7, 2017 at 18:33
• @hyperneutrino looking at the answers on both challenges, it looks like the difference is a single number in the source code, 2 vs 3. I would hardly call that a big difference. Aug 7, 2017 at 18:37
• @WheatWizard For example, if you compare the Jelly answer on that one: ÆEḟ0⁼7B¤ to the Jelly answer on this one: ÆfL=2, you'll notice that there is a significant difference; namely, that one has to check for distinctness. Aug 7, 2017 at 18:41
• @LordFarquaad Just because its a duplicate doesn't mean it is bad. In my mind being a duplicate is a good thing, it means that you are asking a thing that the community finds interesting enough to have already asked about. Aug 7, 2017 at 18:50

# 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

• Right language for the job indeed :P Aug 7, 2017 at 18:55
• @Uriel Ċ is actually a built-in list of two variables; being a declarative language the output is, by default, a test for satisfaction (e.g. ḋ on its own would output true. for non-negative integers). Aug 7, 2017 at 19:10
• How is this 2 bytes? Aug 8, 2017 at 20:19
• @harold I just updated to make "bytes" in the header link to Brachylog's code-page. A hex dump would be c6 eb. Aug 8, 2017 at 20:21

# 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?


# 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.

• Darn it, shorter builtins! :( Aug 7, 2017 at 18:28

# Mathematica, 16 bytes

PrimeOmega@#==2&


PrimeOmega counts the number of prime factors, counting multiplicity.

• Dang, there's a builtin? Aug 8, 2017 at 1:01
• @JungHwanMin If only there was SemiprimeQ Aug 8, 2017 at 1:17
• Nice. I didn't know about PrimeOmega Aug 8, 2017 at 6:00

# 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

• This claims 8 is semiprime
– xnor
Aug 7, 2017 at 19:47
• n**(1/3)%1>0<sum... should work. Aug 7, 2017 at 21:20
• @xnor fixed it.
– Rod
Aug 7, 2017 at 22:55
• Made a tiny edit (e.g. 6 cubed has many more divisors) Aug 8, 2017 at 19:04

# 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.

• Why not just have c start at 0 and count up, instead of making it an array that you add all the factors to? That way you take out the need to use size at the end Aug 8, 2017 at 1:20
• You are right, it's because I wrote the factorization function for another challenge and I reused it here.
– G B
Aug 8, 2017 at 6:10

# Mathematica, 31 29 bytes

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


# Neim, 4 bytes

𝐏𝐥δ𝔼


Try it online!

• Can you explain how this is 4 bytes?... I am totally confused. Aug 7, 2017 at 18:39
• Lol I just had this Aug 7, 2017 at 18:39
• @Mr.Xcoder Neim has a custom code-page Aug 7, 2017 at 18:39
• @Mr.Xcoder Using the Neim codepage, this is 𝐏, 𝐥, δ, and 𝔼 as single-bytes. Aug 7, 2017 at 18:39
• @HyperNeutrino I just obfuscated the 2 a little bit, and now this is the only answer without 2 :)
– Okx
Aug 7, 2017 at 18:40

# 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)

• Did you use the code from Dennis' answer? If so, you should give credit. Aug 7, 2017 at 19:26
• @totallyhuman Oh yeah, sorry. I used it in 2 different answers today and I gave him credit in one of them, but I have forgotten to do that here once more. Thanks for spotting that! Aug 7, 2017 at 19:28
• 67 bytes Aug 7, 2017 at 20:25
• @JonathanAllan Wow, thanks a lot! Aug 7, 2017 at 20:27
• 55 bytes Aug 8, 2017 at 9:05

## 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,
)

# Mathematica 32 bytes

Thanks to ngenesis for 1 byte saved

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

• Save one byte by using ;; instead of All. Aug 7, 2017 at 21:30

# Jelly, 5 bytes

ÆfL=2


Try it online!

# Explanation

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


# Actually, 4 bytes

ol2=


Try it online!

# 05AB1E, 4 bytes

Òg2Q


Try it online!

How?

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


# MATL, 5 bytes

Yfn2=


Try it online!

# Explanation

• Yf - Prime factors.

• n - Length.

• 2= - Is equal to 2?

# 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?

# 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?

• 4 bytes seems to be a common length, I wonder why... - Probably because all answers are prime factors, length, is equal to 2? Aug 8, 2017 at 8:23
• @MrXcoder Yep, exactly Aug 8, 2017 at 11:22
• 4 of which are mine BTW >_> Aug 8, 2017 at 11:23
• 4 is also the first semiprime. Spooky!
– Neil
Aug 8, 2017 at 11:47

# 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!

• lambda n:primeomega(n)==2 Aug 8, 2017 at 3:41
• Ah that reminds me to upgrade from 1.0, thanks! Aug 8, 2017 at 4:01

# 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!

# 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.

• You can remove the else statement (which could be else++r;) to save 8 bytes n->{int r=1,c=2;for(;r++<n;)for(;n%r<1;n/=r)c--;return c==0;}. Aug 9, 2017 at 13:26
• This ties with my regex solution at 61 bytes. Feb 23 at 2:44
• @Deadcode Actually, yours can be 10 bytes shorter by changing new String(new char[n]) to "x".repeat(n) (Java 11+). :) Feb 23 at 8:21
• Ah, nice! It even works in TIO. Hmm... I know I saw this method before, as I had already upvoted this. Can't think of any reason I wouldn't have just included both, unless it didn't work on TIO back then... but TIO already stopped being updated by then, so I don't know. Feb 23 at 16:35

# J-uby + prime, 34 bytes

:prime_division|:*&:pop|:sum|:==&2


Try it online!

# Regex (ECMAScript or better), 24 23 bytes

(?=((x(x*))\2+)\1+$)\3^  -1 byte thanks to Grimmy Try it online! - ECMAScript Try it online! - Python Try it online! - Ruby Takes its input in unary, as a string of x characters whose length represents the number. This regex is based on the 18 byte "Is it prime?" regex (?=(x(x*))\1+$)\2^, which unlike its semiprime version above, is longer than the shortest known, the 16 byte ^(?!(xx+)\1+$)xx. But like ^(?=(xx+?)\1*$)\1$ (also 18 bytes), it has the interesting attribute of implicitly rejecting 0 and 1 as prime numbers, whereas the 16 byte regex must explicitly reject them (the xx at the end).  # tail = N = input number; there's no need to anchor here, # because a start anchor is used at the end of this regex (?= ( # \1 = largest proper divisor of N that is >=2 (x(x*)) # \2 = largest proper divisor of \1; \3 = \2 - 1 \2+ # Assert that \2 is a proper divisor of \1 ) \1+$          # Assert that \1 is a proper divisor of N
)
\3^               # Assert that \3==0, and thus \2==1, meaning the largest proper
# divisor of the largest proper divisor of N is 1, meaning N is
# semiprime


^(?>((x(x*))\2+)\1+$)\3  Try it online! - Perl Try it online! - Java Try it online! - PCRE Try it online! - Python import regex Try it online! - .NET This is a direct port of the "ECMAScript or better" regex above, using an atomic group instead of an atomic lookahead. It is much faster on most regex engines, as the ^ start-anchor test is done first instead of last. # Regex (Perl / Java / PCRE / Pythonregex), 23 bytes ^((x+)\2*(?=\2$)){2}+x$ Try it online! - Perl Try it online! - Java Try it online! - PCRE Try it online! - Python import regex This is a port of the now-obsoleted 24 byte "ECMAScript or better" regex, using a possessive quantifier instead of an atomic lookahead to disable backtracking. ^ # tail = input number ( (x+) # \2 = largest strict divisor of tail # = tail / {smallest prime factor of tail} \2*(?=\2$)      # Assert that \2 is a strict divisor of tail; tail = \2
){2}+               # Execute the loop exactly 2 times, with backtracking disabled
x$# assert tail == 1  ## $$\Expressions\ with\ interactive\ input\$$ # R, 5958 54 bytes grepl('^((.+)\\2*(?=\\2$)){2}+.$',strrep(1,scan()),,1)  Try it online! - test cases only ## $$\Anonymous\ functions\$$ # R, 636258 53 bytes \(n)grepl('^((.+)\\2*(?=\\2$)){2}+.$',strrep(1,n),,1)  Attempt This Online! -1 byte thanks to Giuseppe -4 bytes by using grepl() instead of sum(grep()) or any(grep()) -5 bytes by using a new anonymous function syntax introduced in R v4.1.0 The old 58 byte R v3.5.2 function: Try it online! # Ruby, 37 36 bytes ->n{?x*n=~/(?=((x(x*))\2+)\1+$)\3^/}


Try it online!
Try it online! - test cases only

# PHP, 62 bytes

fn($n)=>preg_match('/^((.+)\2*(?=\2$)){2}+.$/',str_pad('',$n))


Try it online!

n=>/(?=((.(.*))\2+)\1+$)\3^/.test(Array(n+1))  Try it online! # Java 8, 61 bytes n->new String(new char[n]).matches("((.+)\\2*(?=\\2$)){2}+.")


Try it online!
Try it online! - test cases only

^(?>((1(1*))\2+)\1+$)\3  Try it online! - test cases only # PHP, 64 bytes <?=preg_match('/^((.+)\2*(?=\2$)){2}+.$/',str_pad('',$argv));


Try it online!

• I'll forgive you for missing this conversation. 23 bytes Jun 2 at 19:00
• @H.PWiz Oh! Thanks. I came up with (?=(x(x*))\1+$)\2^ independently on 2021-03-06 (basing it on my earlier finding of ^(?>(x(x*))\1+$)\2 on 2018-12-07), and didn't realize Grimmy had already come up with it on 2019-04-21. Cool that a method that's longer for primes can be shorter for semiprimes. Jun 4 at 19:43

# 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!

# Vyxal, 3 bytes

ǐḢ₃


Try it Online!

# Factor + math.primes.factors, 22 bytes

[ factors length 2 = ]


Try it online!

# 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.

# 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  # Pari/GP, 17 bytes n->bigomega(n)==2  Try it online! # 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.

# 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