Primes and Twin Primes

Question

Your challenge is to write a program to print all the primes (separated by one or more whitespace characters) less than a given integer N with an asterisk (*) next to each twin prime. A twin prime is a prime number that is either two more or two less than another prime.

(Hardcoding outputs is allowed, but it is not likely to result in very short code.)

Shortest code wins!

Input

• N is always one of 50, 100, 1000, 1000000, or 10000000

Output

• The output for input 50 should be

  2 3* 5* 7* 11* 13* 17* 19* 23 29* 31* 37 41* 43* 47

Answer 1

Python 2, 81 79 bytes

-2 bytes thanks to dingledooper with a different way to detect if k-2 is a prime which works with k=2.

Uses Wilson's theorem for the primality tests and the fact that \$p\$, \$p+1\$ and \$p+2\$ are coprime for most primes \$p\$.

P=k=q=1
exec"if P%k:print`k`+'*'[k<3:P%(k+2)|q/k];q=k+2\nP*=k*k;k+=1\n"*input()

Try it online!

The output includes the input if it is prime, but this is fine since all testcases are composite.

How?

We use the following result of Wilson's theorem:

$$ (k-1)!^2 \operatorname{mod} k = \begin{cases} 1 & \text{if $k$ is prime}\\ 0 & \text{otherwise.} \end{cases} $$

In the code P is used to keep track of \$(k-1)!^2\$ and P%k tests if k is a prime. If this is the case, we print the output and update q to k+2. If k==q at the print statement, we know that k-2 was a prime and k is a twin prime.

P%(k+2) tests if k+2 is a prime number. If we would use the exact same prime test as before, this would be P*k*k*(k+1)*(k+1)%(k+2), but with our assumption that \$k\$, \$k+1\$ and \$k+2\$ are coprime for prime \$k\$, this gives the same result.
The assumption doesn't hold for k=2, but this is handled separately with '*'[k<3:], which results in the empty string if k<3.

Answer 2

Python 2, 92 bytes

The Sieve of Eratosthenes is used to compute primes. The main advantage here is its incredible speed (N=10000000 is computed in just a few seconds).

n=input()
R=range(n)
for k in R:
 if k>1:R[k+k::k]=(n+~k)/k*[0];print`k`+'*'[:R[k-2]|R[k+2]]

Try it online!

Answer 3

Jelly, 16 bytes

ÆRµ+Ø+Ḥ¤ẒẸ”*xṭ)K

Try it online!

How it works

ÆRµ+Ø+Ḥ¤ẒẸ”*xṭ)K - Main link. Takes N on the left
ÆR               - Yield the prime range until N
  µ           )  - Over each prime P between 2 and N:
       ¤         -   Group into a nilad:
    Ø+           -     Builtin; [1, -1]
      Ḥ          -     Unhalve; [2, -2]
   +             -   Add to P;  [P+2, P-2]
        Ẓ        -   Is prime?
         Ẹ       -   Are any true? Either 1 or 0
          ”*x    -   Repeat "*" that many times
             ṭ   -   Append to P, yielding [P, "*"] or [P, ""]
               K - Join by spaces

Answer 4

APL (Dyalog Extended), 32 26 bytes (SBCS)

Anonymous tacit prefix function.

(⍕,⍬⍴'*'/⍨1⍭¯2 2+⊢)⍤0∘⍸1⍭⍳

Try it online!

⍳ ɩntegers 1 through N

1⍭ Boolean mask indicating those that are primes

⍸ ⍳ ɩndices of the trues (i.e. the primes)

∘ then

(…)∘0 on each scalar, apply the following tacit function:

 ⊢ the argument

 ¯2 2+ add [-2,2] to that

 1⍭ indicate the primes

 '*'/⍨ use that to replicate an asterisk (gives "" or "*" or "**")

 ⍬⍴ reshape into a scalar (lit. an array with an empty shape; gives ' ' or '*' or '*')

 ⍕, prepend the string representation of the argument prime

 since the inner function mapped scalars to vectors the overall result is a matrix

Answer 5

Jelly, 13 bytes

ÆRðȮạe@2”*xṄ)

A monadic Link that accepts a number and prints the output with a new-line separator.
Uses the fact we never receive input, \$n\$, such that \$n-1\$ or \$n\$ are only on the lower side of a prime pair
(e.g. \$41\$ or \$42\$, which would miss the * from \$41\$).

Try it online! (footer suppresses Link's return value).

How?

ÆRðȮạe@2”*xṄ) - Link: n
ÆR            - primes in [2,n] (call this "Primes")
  ð         ) - for each (p in Primes) do this f(p, Primes):
   Ȯ          -   print p (plus no newline)
    ạ         -   (p) absolute difference (Primes)
       2      -   two
     e@       -   (two) exists in (the absolute differences)?
        ”*    -   '*' character
          x   -   ('*') times (existence of two)
           Ṅ  -   print that (plus a newline)

Answer 6

J, 41 bytes

[:(,&":"0' *'{~1+./@p:2 _2+/])i.&.(p:inv)

Try it online!

how

• i.&.(p:inv) Returns every prime less than or equal to the input.

• 2 _2+/] Create a 2 row table, adding and substracting 2 to each prime. Eg, for n=50:

  4 5 7 9 13 15 19 21 25 31 33 39 43 45 49
  0 1 3 5  9 11 15 17 21 27 29 35 39 41 45
  

• 1...p: Is each a prime?

  0 1 1 0 1 0 1 0 0 1 0 0 1 0 0
  0 0 1 1 0 1 0 1 0 0 1 0 0 1 0
  

• +. Reduce each column by "or":

  0 1 1 1 1 1 1 1 0 1 1 0 1 1 0
  

  This mask tells which are the twin primes.

• ' *'{~ Convert 1 to * and 0 to .

• ,&":"0 For each, append , to the input after converting to string &":"0:

  2  
  3* 
  5* 
  7* 
  11*
  13*
  17*
  19*
  23 
  29*
  31*
  37 
  41*
  43*
  47
  

Answer 7

Python 3.8 (pre-release), 107 bytes

p=lambda x:0<all(x%i for i in range(2,x))<x
f=lambda n:[str(i)+'*'*(p(i-2)|p(i+2))for i in range(2,n)if p(i)]

Subtracted 2 bytes for f=

A port of my solution to the previous challenge, with a slightly better p function.

Try it online!

Answer 8

Japt, -S 32 bytes

o fj
äÏ-X¥2Ãp0
íVíVé '+ Ï?X+'*:X

Try it online!

Notably, this works for the required inputs, but not a few others like 12.

Explanation:

o fj    
o       # Create the range [0 ... input]
  fj    # Keep only the primes
        # Store as U


äÏ-X¥2Ãp0    
ä     Ã      # Create an array by mapping each pair in U through:
 Ï-X         #  Get the difference
    ¥2       #  Check whether it's 2
       p0    # Add 0 to the end of that array
             # Store as V


íVíVé '+ Ï?X+'*:X    #
   Vé                # Rotate V 1 item to the right
 Ví   '+             # Add each item in rotated V with the same index in original V
í                    # For each item in U:
         Ï?          #  If the same index in V is not 0:
           X+'*      #   Add "*" to it
               :X    #  Otherwise don't change it
                     # Implicit output, -S flag joins with spaces

I feel like there's a better way to accomplish Ï?X+'*:X but I haven't found one

Answer 9

PowerShell, 172 bytes

$L=@{};($N=2.."$args")|%{$c=2;$k=$_
for(;($k*$c)-le$N[-1]){if(!($L|% c*y($k*$c))){$L[$k*$c]=1};$c++}}
$x=$N|?{!$l.$_}
$x|%{if((($_+2)-in$x)-or(($_-2)-in$x)){"$_*"}else{$_}}

Try it online!

Thanks to @mazzy for ~70 bytes

Answer 10

PowerShell, 91 bytes

Inspired by Wasif

($x=($N=2.."$args")|?{!($N-lt($c=$_)|?{!($c%$_)})})|%{"$_"+'*'*(($_+2)-in$x-or($_-2)-in$x)}

Try it online!

The script outputs correctly for the allowed input and incorrectly in the general case (see last twins for 12)

Less golfed:

$Numbers = 2.."$args"
$primes = $Numbers | Where {
    $current = $_
    $dividers = $Numbers -lt $current | Where {($current % $_) -eq 0}
    !$dividers       # true if the $current is a prime
}
$primes | ForEach {
    "$_"+'*'*(($_+2) -in $primes -or ($_-2) -in $primes)    # format output number
}

Answer 11

Julia 0.4, 61 bytes

I'm using Julia 0.4 because primes was a built-in
It works with a more recent version of Julia and the package Primes.jl

This approach will fail sometimes when N or N-1 is prime, which isn't the case for any of the requested inputs

x->map(i->print(" $i"*"*"^(i+2∈p||i-2∈p)),(p=primes(x);))

Try it online!

Answer 12

Perl 5, 101 bytes

@p[grep"".(1x$_)!~/^(11+)\1+$/,2..$_]=(1)x$_; 
$_=join$",map$p[$_-2]+$p[$_+2]?"$_*":$_,grep$p[$_],2..@p

Try it online!

Uses the somewhat known /^(11+)\1+$/ regexp to detect primes.

Answer 13

Wolfram Language (Mathematica), 70 bytes

If[FreeQ[NextPrime[a=Prime@#,{-1,1}]-a,2|-2],a,a""]&/@Range@PrimePi@#&

Try it online!

-1 byte from @att

Answer 14

JavaScript, 136 119 bytes

n=>(a=(R=n=>[...Array(n).keys()])(n)).filter(x=>a[~x]=+R(x).filter(y=>x%y<1)).map(x=>x+" *"[a[~x+2]|a[~x-2]]).join(' ')

f=
n=>(a=(R=n=>[...Array(n).keys()])(n)).filter(x=>a[~x]=+R(x).filter(y=>x%y<1)).map(x=>x+" *"[a[~x+2]|a[~x-2]]).join(' ')
console.log(f(100));

Saved 17 bytes thanks to tsh

Answer 15

R, 99 87 bytes

With some help from Robin and improvements from Dominic:

for(n in 2:scan())if(sum(!n%%2:n)<2)cat("
",n,"*"[sum(!n%%2:n-2)==1|!sum(!(n+2)%%2:n)])

or, when detailed:

for(n in 2:scan()) #range
  if(sum(!n%%2:n)<2)#prime number
    cat(" #create space
    ",n, #print n
    "*"[sum(!n%%2:n-2)==1| #print * for previous prime
    !s(!(n+2)%%2:n)]} # or for next prime

Try it online!

Answer 16

Husk, 24 22 bytes

Edit: -2 bytes thanks to Razetime

m?o`:'*ssȯ#2`m₁¹≠₁
fṗḣ

Try it online!

Husk doesn't particularly like mixing numerics + characters.

fṗḣ                   # helper function: primes up to input
m?o`:'*ssȯ#2`m₁¹oa-₁  # main function:
m                  ₁  # for each element in primes up to input
                oa-   # get the absolute differences to 
            `m₁¹      # all primes up to input
         ȯ#2          # and count how many '2's there are:
 ?                    # if it's zero
        s             # convert it to a string
  o`:'*s              # otherwise convert it to a string & prepend with '*'

Answer 17

R, 88 87 bytes

p=2;for(y in 3:scan())p=c(p,y[sum(!y%%2:y)<2]);for(z in p)cat(z,"*"[2%in%abs(z-p)]," ")

Try it online!

I wanted to try a different approach to Xi'an's answer...

Frustratingly, though, after golfing & golfing I still can't get rid of that last pesky byte... Got it!

Answer 18

JavaScript (Node.js),  81  80 bytes

A port of ovs' answer. Expects a BigInt.

n=>{for(s=p=k=2n;k<n;p*=k++)p%k?s+=' '+(x=k-2n,p/x%x+p%~-~k?k+'*':k):0;return s}

Try it online!

Or 77 bytes with eval(), as suggested by @EliteDaMyth:

n=>eval("for(s=p=k=2n;k<n;p*=k++)p%k?s+=' '+(x=k-2n,p/x%x+p%~-~k?k+'*':k):s")

Try it online!

---

JavaScript (V8), 91 bytes

n=>{for(k=1;++k<n;)(g=d=>{for(i=d;i%--d;);return~-d})(i=k)||print(g(i-=2)*g(i+=4)?k:k+'*')}

Try it online!

Answer 19

Raku, 54 bytes

{put map {$_~'*'x?is-prime $_+(2|-2)if .is-prime},^$_}

Try it online!

Answer 20

SageMath, 88 bytes

Added 14 bytes to fix an error kindly pointed out by Kjetil S.

def f(n,b=1,c=2):
 while c<n:a,b,c=b,c,Primes().next(c);print(str(b)+'*'[:2in(b-a,c-b)])

Try it online!

Answer 21

Japt -S, 25 bytes

o fj
äÏ-X¥2
gVí|Vé)ð²_+'*

Try it

o fj       - primes up to N
äÏ-X¥2     - difference of each consecutive primes == 2?
g ... _+'* - add an asterisk to the elements at the indexes obtained with @ :
Ví|Vé)   @ pair array with array rotated then reduce by OR
ð²       @ truthy values when passed trough f(square)

-S flag to join with spaces

Answer 22

05AB1E, 14 bytes

ÅPÐδα2δå'*×øJ»

Try it online.

Or alternatively:

ÅP©ε?®yα2å'*×,

Try it online.

Or alternatively (only works in the legacy version of 05AB1E):

ÅPÐδα2QOĀ'*×+»

Try it online.

All three programs above output newline-delimited.
I have the feeling a 13-byter is possible, but I'm unable to find it thus far.

Explanation:

ÅP              # Push a list of primes in the range [2, (implicit) input-integer]
  Ð             # Triplicate this list
   δ            # Pop two of them, and apply double-vectorized:
    α           #  For each prime, get its absolute difference with the list of primes
      δ         # For each list of absolute differences:
     2 å        #  Check if a 2 is among them (1 if truthy; 0 if falsey)
        '*×    '# Repeat "*" that amount of times as string
           ø    # Create pairs with the remaining list of primes
            J   # Join each pair together to a string
             »  # Join this list by newlines
                # (after which the result is output implicitly)

ÅP              # Push a list of primes in the range [2, (implicit) input-integer]
  ©             # Store it in variable `®` (without popping)
   ε            # For-each over each prime:
    ?           #  Pop and print the prime (without trailing newline)
     ®          #  Push the prime-list from variable `®`
      yα        #  Get for each its absolute difference with the current prime `y`
        2å      #  Check if a 2 is in this list of absolute differences
          '*×  '#  Repeat "*" that amount of times as string
             ,  #  Pop and print this string with trailing newline

ÅPÐδα           # Similar as in the first program above
     2Q         # Check for each inner-most value if it's equal to 2
       O        # Sum all inner list of checks
        Ā       # Check which sums are >= 1
         '*×   '# For each, repeat "*" that amount of times as string
            +   # Append it to each integer in the remaining list of primes
             »  # Join this list by newlines
                # (after which the result is output implicitly)

Answer 23

C, 108 106 bytes

-2 bytes thanks to ceilingcat.

f(n,i,j,d,e){for(d=e=i=2;j=n>i;j/i?printf(i-d-2?" %d":d-e-2?"* %d*":" %d*",i),e=d,d=i:1,i++)for(;i%++j;);}

Try it online!

The only input parameter which the function requires is n. The hardest part was avoiding duplication of * after numbers, and there ought to be a better way to do that.