18
\$\begingroup\$

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
\$\endgroup\$
19
  • 10
    \$\begingroup\$ I think you should get rid of the restrictions for N. \$\endgroup\$
    – rak1507
    Feb 28 at 18:32
  • 2
    \$\begingroup\$ @user101295 I doubt any solution that works for those inputs will not work for all N. \$\endgroup\$
    – rak1507
    Feb 28 at 18:34
  • 1
    \$\begingroup\$ @rak1507 If that is the case, the restrictions would not matter, right? \$\endgroup\$
    – user101295
    Feb 28 at 18:36
  • 2
    \$\begingroup\$ @rak1507 I'm just leaving it there to see if there are any solutions that can make use of it. \$\endgroup\$
    – user101295
    Feb 28 at 18:38
  • 2
    \$\begingroup\$ ok, fair enough \$\endgroup\$
    – rak1507
    Feb 28 at 18:38

23 Answers 23

14
\$\begingroup\$

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.

\$\endgroup\$
10
  • 1
    \$\begingroup\$ Love the input('2\n') construction! \$\endgroup\$
    – Sisyphus
    Feb 28 at 23:13
  • 1
    \$\begingroup\$ +1 for Wilson's theorem. \$\endgroup\$
    – Jonah
    Mar 1 at 5:09
  • 2
    \$\begingroup\$ 79 bytes \$\endgroup\$ Mar 1 at 6:26
  • \$\begingroup\$ From comments (at the moment) we may use as much whitespace as we like, assuming this means we can vary it you can do 78 bytes (or less?). \$\endgroup\$ Mar 1 at 9:30
  • 1
    \$\begingroup\$ @Albert.Lang That's what I thought as well, see my previous 81 byter in the revision history. But now that we don't have an additional special case for k=2 anymore, I don't it is possible to save bytes by removing the square. \$\endgroup\$
    – ovs
    Mar 3 at 7:12
7
\$\begingroup\$

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!

\$\endgroup\$
5
\$\begingroup\$

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
\$\endgroup\$
5
\$\begingroup\$

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

\$\endgroup\$
2
  • \$\begingroup\$ Would testing the existence of 2 in absolute difference to the precomputed primes save some? (Like in my Jelly submission.) \$\endgroup\$ Feb 28 at 23:57
  • 1
    \$\begingroup\$ @JonathanAllan Good idea, but I can't seem to get it any shorter. \$\endgroup\$
    – Adám
    Mar 1 at 8:06
4
\$\begingroup\$

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)
\$\endgroup\$
3
\$\begingroup\$

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
    
\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$
4
  • 2
    \$\begingroup\$ nice try. Wasif, 1) you can write "$_" instead "$($_)"; 2) you use 1 for a prime number and 0 for a composite. Flip: 0 (or $null) for prime and 1 for composite. Then you don't need to fill the hashtable $L \$\endgroup\$
    – mazzy
    Mar 1 at 8:18
  • \$\begingroup\$ @mazzy thank you for the tips. But I am unable to implement your 2nd suggestion using arrays :-( \$\endgroup\$
    – wasif
    Mar 1 at 8:28
  • \$\begingroup\$ Wasif's solution with flipped prime flag :) you can shorten this code even more. For example, you can use an array instead the hashtable $L. \$\endgroup\$
    – mazzy
    Mar 1 at 9:28
  • 1
    \$\begingroup\$ @mazzy you are so nice, thank you very much \$\endgroup\$
    – wasif
    Mar 1 at 9:30
1
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$
3
  • 1
    \$\begingroup\$ Nice trick with multiplication, but I think it should be outputting for all primes up to N, not outputting for only the Nth prime. \$\endgroup\$
    – att
    Mar 1 at 19:51
  • \$\begingroup\$ FreeQ[NextPrime[a=Prime@#,{-1,1}]-a,2|-2] also saves one byte \$\endgroup\$
    – att
    Mar 1 at 19:57
  • \$\begingroup\$ @att yes, you are right. Many of us agree that those restrictions for N were not necessary.... \$\endgroup\$
    – ZaMoC
    Mar 1 at 21:05
1
\$\begingroup\$

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

\$\endgroup\$
2
  • 1
    \$\begingroup\$ (a=[...Array(n).keys()]) => (a=(R=n=>[...Array(n).keys()])(n)); x=>a[~x]=[...Array(x+1).keys()].filter(y=>x%y<1).length==2 => x=>a[~x]=R(x+1).filter(y=>x%y<1).length==2 => x=>a[~x]=+R(x).filter(y=>x%y<1) \$\endgroup\$
    – tsh
    Mar 1 at 7:53
  • \$\begingroup\$ @tsh Thanks for the help. \$\endgroup\$ Mar 2 at 3:50
1
\$\begingroup\$

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!

\$\endgroup\$
3
  • 1
    \$\begingroup\$ Both versions seem to omit the *s on 3, 11, 17, 29, and so on... (the twin primes that are two less than another prime) \$\endgroup\$ Mar 3 at 23:32
  • \$\begingroup\$ Ah, correct, I had misread the question!!! \$\endgroup\$
    – Xi'an
    Mar 4 at 6:38
  • 1
    \$\begingroup\$ 94 bytes... or 87 bytes with a space between each twin-prime and the asterisk next to it... \$\endgroup\$ Mar 4 at 8:54
1
\$\begingroup\$

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 '*'
\$\endgroup\$
2
  • \$\begingroup\$ can be used for absolute difference. \$\endgroup\$
    – Razetime
    Mar 4 at 10:00
  • \$\begingroup\$ @Razetime - Thanks! I kinda knew there was that command, but somehow just couldn't remember what it was... \$\endgroup\$ Mar 4 at 10:25
1
\$\begingroup\$

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!

\$\endgroup\$
2
  • \$\begingroup\$ 81 -> 80 with eval \$\endgroup\$
    – user100752
    Jul 7 at 21:27
  • 1
    \$\begingroup\$ @EliteDaMyth Thanks. I saved a few more bytes. \$\endgroup\$
    – Arnauld
    Jul 7 at 21:39
0
\$\begingroup\$

Raku, 54 bytes

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

Try it online!

\$\endgroup\$
0
\$\begingroup\$

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
}
\$\endgroup\$
0
\$\begingroup\$

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!

\$\endgroup\$
2
  • \$\begingroup\$ All primes 3-19 should have * according to the challenge since they have a prime neighbor just 2 away. \$\endgroup\$
    – Kjetil S.
    Mar 1 at 17:24
  • \$\begingroup\$ @KjetilS. Fixed - thanks! :) \$\endgroup\$
    – Noodle9
    Mar 1 at 17:45
0
\$\begingroup\$

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
\$\endgroup\$
0
\$\begingroup\$

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!

\$\endgroup\$
0
\$\begingroup\$

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)
\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.