# Is it a Chen prime?

A number is a Chen prime if it satisfies two conditions:

• It is prime itself
• Itself plus two is either a prime or a semi-prime.

A prime is a number where it has exactly two divisors and those divisors consist of itself and one.

A semi-prime is a number which is the product of two primes. (Note that 12 = 2*2*3 is not semi-prime, but 25 = 5*5 is).

Your task is to determine if a number is a Chen prime. You should output any truthy value for yes and any falsy value for no.

The input will be any integer greater than or equal to one. It may also be taken as a string, character array, or an array or digits.

## Examples:

101 -> truthy
223 -> falsy
233 -> truthy
1 -> falsy


This is OEIS A109611.

This is, in part, inspired by Am I a Sophie Germain prime? which, unfortunately, got closed as a duplicate, so I'm posting a somewhat related challenge which isn't a duplicate.

• Can we return True for truthy and 2 or False for falsy (inconsistent falsy values)? Jul 10 '17 at 12:04
• @Mr.Xcoder Never said you couldn't
– Okx
Jul 10 '17 at 12:06
• For a semi-prime, does "exactly two prime factors" count multiplicity? Is 2 * 2 * 2 * 3 * 3 a semi-prime? What about 5 * 5? Jul 10 '17 at 12:09
• @Notatree 5*5 is semi-prime, 2*2*2*3*3 is not. I said exactly two.
– Okx
Jul 10 '17 at 12:11
• So it does count multiplicity, then? (You could argue that 2*2*2*3*3 has exactly two prime factors, namely 2 and 3, and 5*5 has one prime factor, namely 5.) Maybe you could edit that into the question? Jul 10 '17 at 12:17

# Brachylog, 7 bytes

ṗ+₂ḋl≤2


Try it online!

### Explanation

ṗ         Input is prime
ḋ      The prime factorization of…
+₂       … Input + 2…
l≤2   … has 2 or less elements

• I caught Neil at exactly 48,000 rep, and now you at exactly 22,222 :P Jul 10 '17 at 16:29

# 05AB1E, 8 bytes

p¹ÌÒg3‹*


Try it online!

### Explanation

p¹ÌÒg3‹*   Argument n
p          Push isPrime(n)
¹ÌÒ       Push list of prime factors of (n+2)
g3‹    Length of list is lower than 3
*   Multiplication of boolean values, 0 if either is 0 (false)


# Pyth, 10 bytes

&P_Q>3lP+2


Try it online!

How?

&P_Q>3lP+2  # input: Q
+2  # Q + 2
P    # prime factors
>3l     # length lower than 3?
P_Q        # Q is prime?
&           # and both results

• >.< Outgolfed >.< Jul 10 '17 at 12:17
• @Mr.Xcoder actually, I posted mine 5 minutes before Jul 10 '17 at 12:19
• Yeah, didn't see it because of the poor internet connection Jul 10 '17 at 12:23

# ArnoldC, 1339 bytes

LISTEN TO ME VERY CAREFULLY q
GIVE THESE PEOPLE AIR
HEY CHRISTMAS TREE c
YOU SET US UP 0
HEY CHRISTMAS TREE d
YOU SET US UP 0
HEY CHRISTMAS TREE l
YOU SET US UP p
STICK AROUND l
GET TO THE CHOPPER d
HERE IS MY INVITATION p
I LET HIM GO l
ENOUGH TALK
BECAUSE I'M GOING TO SAY PLEASE d
BULLSHIT
GET TO THE CHOPPER c
HERE IS MY INVITATION c
GET UP 1
ENOUGH TALK
YOU HAVE NO RESPECT FOR LOGIC
GET TO THE CHOPPER l
HERE IS MY INVITATION l
GET DOWN 1
ENOUGH TALK
CHILL
I'LL BE BACK c
HASTA LA VISTA, BABY
IT'S SHOWTIME
HEY CHRISTMAS TREE p
YOU SET US UP 0
GET YOUR ASS TO MARS p
DO IT NOW
I WANT TO ASK YOU A BUNCH OF QUESTIONS AND I WANT TO HAVE THEM ANSWERED IMMEDIATELY
HEY CHRISTMAS TREE n
YOU SET US UP 0
GET YOUR ASS TO MARS n
DO IT NOW q p
HEY CHRISTMAS TREE g
YOU SET US UP 42
GET TO THE CHOPPER g
HERE IS MY INVITATION n
YOU ARE NOT YOU YOU ARE ME 2
ENOUGH TALK
BECAUSE I'M GOING TO SAY PLEASE g
GET TO THE CHOPPER p
HERE IS MY INVITATION p
GET UP 2
ENOUGH TALK
GET YOUR ASS TO MARS n
DO IT NOW q p
GET TO THE CHOPPER g
HERE IS MY INVITATION 5
LET OFF SOME STEAM BENNET n
ENOUGH TALK
BECAUSE I'M GOING TO SAY PLEASE g
TALK TO THE HAND "t"
BULLSHIT
TALK TO THE HAND "f"
YOU HAVE NO RESPECT FOR LOGIC
BULLSHIT
TALK TO THE HAND "f"
YOU HAVE NO RESPECT FOR LOGIC
YOU HAVE BEEN TERMINATED


Try it online!

(This is my first post on codegolf.SE, please let me know if this is formatted incorrectly. I realize this byte count is not competitive, this is just for fun.)

# Jelly, 10 bytes

+2ÆfL<3aÆP


Try it online!

# Python with sympy,  69  56 bytes

-13 bytes thanks to alephalpha (by upgrading to sympy 1.1 and using primeomega(n+2) to replace sum(factorint(n+2).values()))

...taking over from Gryphon's deleted submission.

from sympy import*
lambda n:primeomega(n+2)<3*isprime(n)


An unnamed function returning True for Chen primes and False otherwise.

Counts the factors of n+2 by summing its prime factor's multiplicities.

Note that 3 is multiplied by isprime(n) before the < comparison is made, so for non-prime n the code tests if n+2 has less than 0 factors (always yielding False), while for prime n it checks whether n+2 is prime or semi-prime.

• @Gryphon - I took over, it may be beatable without any imports however. Jul 10 '17 at 13:26
• I've been outgolfed! The 3*isprime(n) trick is what I was looking for in cleaning up the conditional statement. Jul 10 '17 at 13:35
• Ah, @icosahedron, I had not noticed yours, sorry - this is so similar I would have just commented to help you to improve yours. Feel free to treat this answer as such, just let me know and I'll delete this one. Jul 10 '17 at 13:46
• I think sympy has a primeomega function. Jul 10 '17 at 13:48
• @alephalpha Thanks, just upgraded to 1.1 to see it, that'll save bytes! Jul 10 '17 at 13:56

# Pari/GP, 29 bytes

The 3*isprime(n) trick is stolen from Jonathan Allan 's answer.

n->bigomega(n+2)<3*isprime(n)


Try it online!

# Java 8, 8584 83 bytes

n->{int a=n+2,b=0,c=0,i=1;for(;i++<n;b+=n%i<1?1:0)c+=a%i<1?1:0;return n>1&b<2&c<3;}


-1 bytes thanks to @OlivierGrégoire by using an iterative approach instead of recursive.

Explanation:

Try it here.

n->{            // Method with integer parameter and boolean return-type
int a=n+2,    //  Start a at the input + 2
b=0,c=0,  //  Start b and c at 0
i=1;      //  Start i at 1
for(;i++<n;   //  Loop from 1 to n (and raise i immediately by 1)
b+=n%i<1?   //   If the input is divisible by i
1       //    Raise b by 1
:        //   Else:
0)      //    Leave b as is
c+=a%i<1?   //   If the input + 2 is divisible by i:
1       //    Raise c by 1
:        //   Else:
0;      //    Leave c as is
//  End of loop (implicit / single-line body)
return n>1    //  Return if the input is larger than 1
&b<2   //   And b is now smaller than 2
&c<3;  //   And c is now smaller than 3
}               // End of method

• The iterative version is just a byte shorter: n->{int N=n+2,f=0,F=0,d=1;for(;d++<n;f+=n%d<1?1:0)F+=N%d<1?1:0;return n>1&f<2&F<3;}. Jul 10 '17 at 22:59

# Mathematica, 28 bytes

PrimeQ@#&&PrimeOmega[#+2]<3&


# JavaScript (ES6), 63 61 bytes

g=(e,i=e)=>i--<3?1:e%i?g(e,i):g(i)+1
f=e=>e>1&g(e)<2&g(e+2)<3
Test cases:<br><textarea id=i rows=6 oninput="go()">101&#10;223&#10;233&#10;1</textarea><br><pre id=q></pre><script>window.onload=function go(){document.getElementById('q').innerHTML=document.getElementById('i').value.split('\n').map(e=>e+' -> '+f(+e)).join('\n')}</script>

Defines a function f that takes n as argument and returns the result. Im very happy with how g turned out; it counts the number of prime factors in a number.

2 bytes saves thanks to Kevin Cruijssen's & trick.

### Ungolfed

Ω = (n,          // Ω(n) = number of n's prime factors, n > 1.
i = n) =>    // Start iterating from i = n - 1. Since we'll immediately
// decrement i, n is used here.
--i          // Immediately decrement i.

< 2          // If i = 0 or i = 1, n is a prime at this point.
? 1 :        // Therefore Ω(n) = 1.

n % i != 0 ? // If n is not divisible by i,
Ω(n, i)      // try again with i := i - 1 (immediately decremented, so use i).

: Ω(i) + 1   // n is divisible by i. Since we're counting down from n - 1
// and i is the first such number, i is n's largest non-trivial
// divisor, and thus n/i is a prime.
// Therefore Ω(n) = Ω(i) + Ω(n/i) = Ω(i) + 1.

is_chen = n =>     // An integer n ≥ 1 is a Chen prime if and only if:
n > 1          // n > 1,
& Ω(n) < 2     // Ω(n) = 1 < 2, i.e. n is a prime, and
& Ω(n + 2) < 3 // Ω(n + 2) < 3, i.e. n + 2 is a prime or a semiprime.

• Can't you change both && to &? Since 0/1 are truthy/falsey values in JS as well? Jul 10 '17 at 13:19
• @KevinCruijssen That seems to work. Too bad | and & don't short-circuit, that might save even more bytes in g. Jul 10 '17 at 13:27

# Japt, 22201913 12 bytes

U°j ©2¨°Uk l

• 6 bytes saved thanks to obarakon's suggestion of a different method.

Test it

# PHP, 64 bytes

for($i=$n=$argn+2;--$i;$argn%$i?:$q++)$n%$i?:++$p;echo$p<4^--$q;


prints 0 for truthy, other integers for falsy. Run as pipe with -nR or try it online.

breakdown

for($i=$n=$argn+2;--$i; # loop $i from N+1 to 1$argn%$i?:$q++)         # if $i divides N, increment$q
$n%$i?:++$p; # if$i divides N+2, increment $p echo$p<4                # $p is 1 for a prime, 3 for a semiprime ^--$q;              # $q is 2 for prime; so this is 1^1 (==0) for a Chen Prime  consistent falsy value, 65 bytes: for($i=$n=2+$k=$argn;--$i;$k%$i?:$q++)$n%$i?:++$p;echo$p<4&$q==2;


prints 1 for truthy and 0 for falsy.

# Regex (ECMAScript), 31 bytes

^(?!((xx+)(\2(xx))*)(\1\4)+$)xx  Try it online! (showing all Chen primes ≤ 1000) Given a string of n xs this regex will match if and only if n is a Chen prime. It asserts that n is greater than 2 and that the string is not of the form ((xx+)(\2(xx))*)(\1\4)+ This regex has two meanings, depending on how many times (\2(xx)) is repeated. When it is repeated 0 times, the regex can be simplified to (xx+)\1+, which matches composite numbers. When it is repeated a positive number of times, the regex is equivalent to ((xx+)(\2xx)+)(\1xx)+ That regex requires some explanation, however, I will provide little insight. If you go through the algebra you find that ((xx+)(\2xx)+)(\1xx)+ matches numbers of the form a*b*c-2 where a≥4,b≥2,c≥2. So it will match (almost) whenever n+2 has more than 2 prime factors. (i.e neither prime nor semi-prime) Note that it doesn't match 6, 10, 16 or 25, but that this doesn't matter, because they are all composite. So (?!((xx+)(\2(xx))*)(\1\4)+$) will match as long as n is not composite, and n+2 is either prime or semi-prime.
Unfortunately this includes 1 (and 0), so we then check that n is at least 2 with xx

A couple of different "31-byters" are:

^xx(?!((x*)(\2xx)+)\1?(\1xx)*$) ^(?!(xx((x*)(\3xx)+))\2?\1*$)xx


# Python 3 with SymPy, 73 71 bytes

lambda n:(sum(factorint(n+2).values())<3)&isprime(n)
from sympy import*


Try it online!

This is a more-golfed version of an answer posted here earlier, but it seems to have been deleted.

Thanks to @JonathanAllan for saving 2 bytes!

• ...also note that you do not need f=, creating an unnamed function is fine for code-golf. Jul 10 '17 at 13:48

for($b=($a=$argn)+$i=2;2<$a+$b;)$a%$i?$b%$i?$i++:++$d*$b/=$i:++$c*$a/=$i;echo$c<2&$d<3;  Try it online! # PHP, 87 bytes for(;$n<2;)for($a=$argn+$n++*$i=2;1<$a;)$a%$i?$i++:++$r[$n]*$a/=$i;echo$r[1]<2&$r[2]<3;


Try it online!

# APL NARS, 23 chars

{1≥⍵:0⋄(1=⍴π⍵)∧3>⍴π⍵+2}


Here π⍵ return the array of factors of ⍵ different from 1; some test:

  f←{1≥⍵:0⋄(1=⍴π⍵)∧3>⍴π⍵+2}
f 101
1
f 223
0
f 233
1
f 1
0
f ¯10
0


# Ruby, 49 41 bytes

->n{/^(.?|((..+)\3+))(\2+|..)$/!~?l*n+=2}  Try it online! Thanks H.PWiz for -8 bytes ### How? First thing, get a string of 'l' repeated n+2 times. Then apply a regex to check if: • Length is 2 or 3 (.?)(..) • Length is a composite number plus 2 ((..+)\1)(..) • Length is a product of at least 3 numbers ((..+)\2)\1+ The 2 regex parts generate a fourth case which doesn't make sense and is safe to ignore: (.?)\2+, that resolves to empty string or a single character because \2 is empty. • You can merge the two halves of your | closer together: ^((..+)\2+)(\1+|..)$. Also, a neat coincidence that you attempted this problem with regex at a similar time to me :) Apr 17 '19 at 23:01
• I believe that you can use . instead of .? since the input is always at least 1 Apr 18 '19 at 11:01

# Husk, 9 bytes

&<3Lp+2¹ṗ


Try it online!

## Explanation

&<3Lp+2¹ṗ
ṗ input is prime?
&         and
L      Length of
p     prime factorization of
+2¹  input + 2
<3       less than 3?


# Julia, 59 bytes

x->((0∉x%(2:x-1))&(length(find(x->x==0,(x+2)%(2:x)))<=2))


# Pyt, 11 bytes

3*isprime(x) stolen from Jonathan Allan's answer

←Đṗ3*⇹2+ḋŁ>


p k=last$(not$elem 0(map(mod k)[2..k-1])):[1>2|k<=1]