4
\$\begingroup\$

Your challenge is to write a program (full program, not a function), that will take an integer and output all prime numbers up to (including) the given integer. Output is any readable list containing all integer primes (array, string, 1 prime per line, whatever you want) and must run to stdout or equivalent.

Simple? Here's the twist:

You may not use literals in your program. These include:

  • Literal numbers (0 through 9)
  • Literal strings (in quotes)

You may not use built in prime checks

EDIT: A prime check is a built in function that

  • Returns if a number is a prime number
  • Returns a prime number
  • Returns a list of prime numbers

You may code your own functions that do the above

Prime factorisation functions are allowed

As this is code-golf, shortest answer in bytes wins

\$\endgroup\$

marked as duplicate by mbomb007, DJMcMayhem, Blue, Julie Pelletier, Bálint Jun 22 '16 at 21:56

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 6
    \$\begingroup\$ This is an occurence of the Do X without Y problem. Not that this question is bad, just wanted to know. \$\endgroup\$ – user48538 May 27 '16 at 9:13
  • 7
    \$\begingroup\$ What about prime-factorization builtins? \$\endgroup\$ – Denker May 27 '16 at 9:49
  • 7
    \$\begingroup\$ You may not use built in prime checks Does that forbid prime factorization as well (i.e. a built-in function that computes prime factors of a number)? \$\endgroup\$ – Luis Mendo May 27 '16 at 10:23
  • 4
    \$\begingroup\$ Do you have a particular reason for disallowing functions? They're allowed by default and arbitrarily overriding the defaults is one of the things to avoid when writing challenges. \$\endgroup\$ – Dennis May 28 '16 at 0:17
  • 5
    \$\begingroup\$ If this were not already closed, I would vote to close it as a duplicate of codegolf.stackexchange.com/q/70001/194 . The accepted answer to that question meets all of the criteria of this one, and the others can be adapted. (Admittedly some would be more costly to adapt than others). \$\endgroup\$ – Peter Taylor May 28 '16 at 9:59

20 Answers 20

8
\$\begingroup\$

05AB1E, 7 6 bytes

Six byte solution

Since prime factorisation is now allowed, this is my six byte solution:

LDÒ€gÏ

Explanation:

L       # Create the list [1, ..., input]
 D      # Duplicate this list
  Ò     # Get the prime factorisation of each number
   €g   # Get the length of each prime factorisation (length 1 = prime)
     Ï  # Keep the numbers for which is the index is equal to 1

Uses CP-1252 encoding. Try it online!.


Previous solution

Uses Wilson's theorem. Code:

LÐ<!n%Ï

Explanation:

L        # Generate the list [1, ..., input].
 Ð       # Triplicate the list.
  <      # Decrement the last one by one.
   !     # Take the factorial.
    n    # Square each.
     %   # Modulo the list by [1, ..., input].
      Ï  # Take the values for which the indices are equal to 1.

Visual explanation for input n = 9:

 Command - Stack

L        # [1, 2, 3, 4, 5, 6, 7, 8, 9]
 Ð       # [1, 2, 3, 4, 5, 6, 7, 8, 9] × 3
  <      # [1, 2, 3, 4, 5, 6, 7, 8, 9] × 2, [0, 1, 2, 3, 4, 5, 6, 7, 8]
   !     # [1, 2, 3, 4, 5, 6, 7, 8, 9] × 2, [1, 1, 2, 6, 24, 120, 720, 5040, 40320]
    n    # [1, 2, 3, 4, 5, 6, 7, 8, 9] × 2, [1, 1, 4, 36, 576, 14400, 518400, 25401600, 1625702400]
     %   # [1, 2, 3, 4, 5, 6, 7, 8, 9], [0, 1, 1, 0, 1, 0, 1, 0, 0]

Which leaves us (using Ï):

[1, 2, 3, 4, 5, 6, 7, 8, 9], 
[0, 1, 1, 0, 1, 0, 1, 0, 0]

    2  3     5     7

Uses CP-1252 encoding. Try it online!.

\$\endgroup\$
6
\$\begingroup\$

Jelly, 10 9 8 7 bytes

1 byte saved thanks to Dennis.

Ṗ!²%ḊT‘

Try it online!

This is my first (working) Jelly program. I have no idea what I'm doing. :P

Also uses Wilson's theorem.

\$\endgroup\$
  • 4
    \$\begingroup\$ I had that same feeling with my first Jelly answer, only in my case it was non-working \$\endgroup\$ – Luis Mendo May 27 '16 at 14:26
6
\$\begingroup\$

05AB1E, 2 bytes

!f

Allowing prime factorization makes this a bit too easy...

Try it online!

How it works

!   Compute the factorial of the input.
 f  Find its prime factors.
\$\endgroup\$
  • \$\begingroup\$ And, as the legend goes, nobody ever out golfs Dennis. \$\endgroup\$ – noɥʇʎԀʎzɐɹƆ Jun 22 '16 at 18:46
5
\$\begingroup\$

Pyth, 11 bytes

f!%h.!tTTtS

Try it online.

Uses Wilson's theorem. Not my own idea (suggested to DenkerAffe by Leaky Nun & used already by Adnan), so I'm making it a community wiki.

\$\endgroup\$
  • \$\begingroup\$ Meh, was planning to do that after work, already spent too much time here on this :P But whatever, well done ;) \$\endgroup\$ – Denker May 27 '16 at 12:14
  • 2
    \$\begingroup\$ I don't know why, but I immediately read this code as fishsticks \$\endgroup\$ – Alexis Andersen May 27 '16 at 14:35
  • \$\begingroup\$ What about {P.!Q ? \$\endgroup\$ – drobilc May 28 '16 at 12:43
  • \$\begingroup\$ @drobilc P would be a prime builtin which are disallowed. \$\endgroup\$ – PurkkaKoodari May 28 '16 at 15:34
  • \$\begingroup\$ @Pietu1998 Yes, but I'm using P as a prime factorisation function, which is allowed. \$\endgroup\$ – drobilc May 28 '16 at 18:25
3
\$\begingroup\$

Ruby, 53

$..upto(gets.to_i){|i|($....i).one?{|f|i%f<$.}&&p(i)}

This uses the $. magic variable in place of numeric literals, since it starts off as 0 and is incremented when we call gets to read from standard input. We can then define a prime number as a number that has exactly one factor less than it ($....i means the range from 1 to i excluding i) to avoid erroneously printing 0 and 1.

\$\endgroup\$
  • \$\begingroup\$ I didn't realize that Ruby copied the $. variable from Perl. \$\endgroup\$ – Brad Gilbert b2gills May 27 '16 at 16:10
3
\$\begingroup\$

JavaScript (ES6), 98 bytes

alert([...Array(-~(n=prompt())).keys()].filter(n=>n>!!n&&[...Array(n)].ev‌​ery((_,i)=>i==!!i||n%i)))

f=n=>[...Array(-~n).keys()].filter(n=>n>!!n&&[...Array(n)].every((_,i)=>i==!!i||n%i))
<input id=i oninput=o.value=f(i.value)><input id=o>

\$\endgroup\$
  • \$\begingroup\$ Would it be shorter to use regex matching? \$\endgroup\$ – Leaky Nun May 27 '16 at 9:40
  • \$\begingroup\$ I think n=>[...(a=Array)(-~n).keys()].filter(n=>n>!!n&&[..a(n)].every((_,i)=>i==!!i||n%i)) is shorter \$\endgroup\$ – Bálint May 27 '16 at 10:24
  • \$\begingroup\$ @Bálint Only because you accidentally deleted one of the .s before the a. \$\endgroup\$ – Neil May 27 '16 at 10:29
  • \$\begingroup\$ From the description of the challenge, on the first line: "Your challenge is to write a program (full program, not a function) [...]". You currently have a function, not a full program. A full program would be (n=>[...Array(-~n).keys()].filter(n=>n>!!n&&[...Array(n)].every((_,i)=>i==!!i||n%i)))(prompt()). I will reverte the downvote once any necessary change is made. \$\endgroup\$ – Ismael Miguel May 27 '16 at 13:33
  • \$\begingroup\$ That is still just a function, but, I removed the downvote since the question was closed. \$\endgroup\$ – Ismael Miguel May 29 '16 at 18:50
2
\$\begingroup\$

Retina, 29 27 bytes

!&`(?!.$|(?<k>..+)\<k>+$).+

Try it online!

Input/output in unary.

How it works:

It matches, with overlapping (&), the substrings of the input that are not 1 ((?!.$) and are not composite numbers ((?<k>..+)\<k>+$), then output all matches linefeed-separatedly (!)

\$\endgroup\$
2
\$\begingroup\$

Pyth, 13 bytes

fqh!Z/%LTSTZS

Try it here!

Explanation

Using the shortest (but most inefficient) way to check for primes.

fqh!Z/%LTSTZSQ    # implicit: Q = input

f           SQ    # Filter [1...Q] with T
       L ST       # Map over [1...T]
      % T         # T module the lambda var
     /     Z      # Count number of zeroes
 qh!Z             # If ^ is 2, it's a prime
\$\endgroup\$
  • \$\begingroup\$ Would it be shorter to use Wilson's theorem? \$\endgroup\$ – Leaky Nun May 27 '16 at 9:40
  • \$\begingroup\$ Checking if a number is equal to 2 can be done with: !tt \$\endgroup\$ – Jakube May 27 '16 at 22:30
2
\$\begingroup\$

MATL, 10 bytes

:t!\~sqq~f

Try it online!

It could be shortened to 9 bytes using H (which produces predefined literal 2). But it feels like cheating:

:t!\~sH=f

Try it online!

Explanation

:     % Implicitly take input N. Generate row vector [1 2 ... N]
t!    % Duplicate and transform into column vector
\     % Modulo operation, element-wise with broadcast
~     % Logical negate. Transform zeros to 1, non-zeros to 0
s     % Sum of each column
qq    % Decrement by 1, twice. Zeros correspond to primes
~f    % Indices of zeros. Implicitly display
\$\endgroup\$
1
\$\begingroup\$

Perl 6,  51 48  47 bytes

.say for grep {!first $_%%*,[*]^.. .sqrt},[*]^..get
.say for grep {!first $_%%*,[*]^..^$_},[*]^..get
.say for grep {!grep $_%%*,[*]^..^$_},[*]^..get

Explanation:

[*] / [*] () multiply all of the elements of an empty list, which results in 1.

$_ %% * is a WhateverCode that returns True if $_ is divisible by its only argument.

.say   # call the .say method on:
for    # every value from:
  grep # only those that match:

    {  # bare block with $_ for parameter
       # ( this block returns True when the value is prime )
      !          # negate: ( True for Nil, False for a number )

      first      # return the first value that is
        $_ %% *, # divisible by one of the following

        # 「2 .. $_.sqrt.floor」

        [*]      # 1
        ^..      # Range that ignores the first value
        .sqrt    # the square root of the value we are checking for primality
    },

    # 「2 .. get」

    [*]         # 1
    ^..         # Range that ignores the first value
    get         # read a line from $*IN

The 48 byte example tests against a Range that is from 1 up to the value to check for primality, excluding both end points.


That will run slower as the prime numbers increase, as it checks against all values up to the square root of the number it is testing. It will be more performant if you cache the primes as you go, and only test against them.
( There may be a point where the previous code will be more performant if you run out of memory, and it has to page the cache out to disk )

my @p;.say for grep {push @p,$_ if !first $_%%*,@p},([*])^..get

The normal way to write something that prints out primes would be:

.say for grep *.is-prime, 2..get

( I would probably use @*ARGS[0] instead of get so that it gets input from the command line instead of STDIN )

\$\endgroup\$
  • \$\begingroup\$ my @p;.say for grep {push @p,$_ if !first $_%%*,@p[{0..$_/2}]},([*])^..get would be even more performant \$\endgroup\$ – Brad Gilbert b2gills May 27 '16 at 16:43
1
\$\begingroup\$

J, 22 bytes

([:>:@I.>:|*:@!)@i.@x:

Also uses Wilson's theorem.

Usage

   f =: ([:>:@I.>:|*:@!)@i.@x:
   f 9
2 3 5 7
   f 100
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
\$\endgroup\$
1
\$\begingroup\$

Python 2, 74 bytes

lambda n:[-p for p in range(-n,n/-n)if all(p%i for i in range(-~True,-p))]
\$\endgroup\$
  • \$\begingroup\$ Is this a function? \$\endgroup\$ – Tim May 28 '16 at 0:41
1
\$\begingroup\$

JavaScript (ES6), 110 bytes

f=n=>{p=true;q=[];for(i=p+p;i<=n;i++){for(j=i/i;++j<i;p=i%j?p:p>p);p?q.push(i):i;p=true}alert(q)};f(+prompt())

Thanks to @LeakyNun for helping me shorten my solution.

\$\endgroup\$
  • \$\begingroup\$ i=true+true -> i=p+p \$\endgroup\$ – Leaky Nun May 27 '16 at 14:08
  • \$\begingroup\$ for(j=true+true;j<i;j++)i%j==false?p=false:null; -> for(j=i/i;++j<i;p=i%j?p:p<p); \$\endgroup\$ – Leaky Nun May 27 '16 at 14:23
  • \$\begingroup\$ p?q.push(i):null; -> p+=p?","+i:""; \$\endgroup\$ – Leaky Nun May 27 '16 at 14:27
  • \$\begingroup\$ for(...){} -> for(...); \$\endgroup\$ – Leaky Nun May 28 '16 at 1:09
  • \$\begingroup\$ for(i=p+p;i<=n;p?q.push(i):i,i++)for(p=true,j=p;++j<i;p=i%j?p:p>p); \$\endgroup\$ – Leaky Nun May 28 '16 at 1:15
1
\$\begingroup\$

Brachylog, 6 bytes

$!$pd.

Saved a crapload of bytes thanks to @LeakyNun, who pointed out that you can use prime factorization built-ins.

\$\endgroup\$
  • \$\begingroup\$ $!$pd should save some bytes \$\endgroup\$ – Leaky Nun Jun 22 '16 at 14:01
  • \$\begingroup\$ @LeakyNun Since the rule about prime built-ins was unclear, I chose not to use any, prime factorization included. It would save bytes though, that's for sure. \$\endgroup\$ – Fatalize Jun 22 '16 at 14:16
  • \$\begingroup\$ The question said prime factorization is allowed. \$\endgroup\$ – Leaky Nun Jun 22 '16 at 14:18
  • \$\begingroup\$ @LeakyNun Thanks. \$\endgroup\$ – Fatalize Jun 22 '16 at 14:35
0
\$\begingroup\$

Python 2, 102 bytes

p=input()
q=p/p
print[i if min([i%l for l in range(q+q,i)]+[q])>q-q else None for i in range(q+q,p+q)]
\$\endgroup\$
0
\$\begingroup\$

Python 2, 59 58 bytes

n=input();k=p=n/n
while k<n:
 p*=k*k;k=-~k
 if p%k:print k

Test it on Ideone.

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

Perl 5, 37 bytes

36, plus 1 for -nE instead of -e

{/^.?$|^(..+?)\1+$/||say;s/.//;redo}

Input and output are in unary.

\$\endgroup\$
  • \$\begingroup\$ If \1 is considered using a literal number, I can use \g1 instead at the expense of a byte. But it shouldn't be so considered: it's really a variable name. \$\endgroup\$ – msh210 May 30 '16 at 3:15
0
\$\begingroup\$

Mathematica, 43 bytes

Select[Range@Input[],Tr@Rest@Divisors@#==#&]

Selects from a range of integers between 1 and Input[] those, the sum of whose divisors, except the first one (in ascending order) is equal to the number itself.

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

J, 7 bytes

~.@q:@!

~. unique @ of q: prime factors @ of ! factorial

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

Dyalog APL, 14 bytes

((⊢~∘.×⍨)≢↓⍳)⎕

Fully parenthesised:

(⊢ ~ ((∘.×)⍨)) (≢ ↓ ⍳)

Every triple of functions applies the right and left monadic functions separately to whatever is outside of the parenthesis, and then the two results become the arguments of the middle function, thus (f g h)A is (f A) g (h A). This repeat itself until the following tree structure:

    ┌──────┴──────┐
 ┌──┼────┐     ┌──┼──┐
┌┴┐┌┴┐┌──┴──┐ ┌┴┐┌┴┐┌┴┐
│⊢││~││∘.× ⍨│ │≢││↓││⍳│
└─┘└─┘└─────┘ └─┘└─┘└─┘

prompt for numeric input

Let's assume the user inputs 6:

tally the input (giving 1) and indices until the input (giving 1 2 3 4 5 6)

1 ↓ 1 2 3 4 5 6 drop 1 from the list (giving 2 3 4 5 6)

pass through (2 3 4 5 6) and ∘.×⍨ multiplication table:

 4  6  8 10 12
 6  9 12 15 18
 8 12 16 20 24
10 15 20 25 30
12 18 24 30 36

2 3 4 5 6 ~ 4 6 8 10 12 6 9… "without" (i.e. set difference), yielding 2 3 5

TryAPL!

\$\endgroup\$

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