Illiteral Prime numbers [duplicate]

Question

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

Answer 1

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

Answer 2

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.

Answer 3

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.

Answer 4

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.

Answer 5

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.

Answer 6

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>

Answer 7

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 (!)

Answer 8

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

Answer 9

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

Answer 10

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 )

Answer 11

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

Answer 12

Python 2, 74 bytes

lambda n:[-p for p in range(-n,n/-n)if all(p%i for i in range(-~True,-p))]

Answer 13

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.

Answer 14

Brachylog, 6 bytes

$!$pd.

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

Answer 15

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

Answer 16

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.

Answer 17

Perl 5, 37 bytes

36, plus 1 for -nE instead of -e

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

Input and output are in unary.

Answer 18

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.

Answer 19

J, 7 bytes

~.@q:@!

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

Answer 20

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!