# Illiteral Prime numbers [duplicate]

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

• This is an occurence of the Do X without Y problem. Not that this question is bad, just wanted to know. Commented May 27, 2016 at 9:13
• What about prime-factorization builtins? Commented May 27, 2016 at 9:49
• 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)? Commented May 27, 2016 at 10:23
• 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. Commented May 28, 2016 at 0:17
• 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). Commented May 28, 2016 at 9:59

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

# Jelly, 1098 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.

• I had that same feeling with my first Jelly answer, only in my case it was non-working Commented May 27, 2016 at 14:26

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

• And, as the legend goes, nobody ever out golfs Dennis. Commented Jun 22, 2016 at 18:46

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

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

# 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. • I didn't realize that Ruby copied the $. variable from Perl. Commented May 27, 2016 at 16:10

## 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>

• Would it be shorter to use regex matching? Commented May 27, 2016 at 9:40
• I think n=>[...(a=Array)(-~n).keys()].filter(n=>n>!!n&&[..a(n)].every((_,i)=>i==!!i||n%i)) is shorter Commented May 27, 2016 at 10:24
• @Bálint Only because you accidentally deleted one of the .s before the a.
– Neil
Commented May 27, 2016 at 10:29
• 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. Commented May 27, 2016 at 13:33
• That is still just a function, but, I removed the downvote since the question was closed. Commented May 29, 2016 at 18:50

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

# 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

• Would it be shorter to use Wilson's theorem? Commented May 27, 2016 at 9:40
• Checking if a number is equal to 2 can be done with: !tt Commented May 27, 2016 at 22:30

# 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


# 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 ) • my @p;.say for grep {push @p,$_ if !first $_%%*,@p[{0..$_/2}]},([*])^..get would be even more performant Commented May 27, 2016 at 16:43

# 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


# Python 2, 74 bytes

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

• Is this a function?
– Tim
Commented May 28, 2016 at 0:41

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

• i=true+true -> i=p+p Commented May 27, 2016 at 14:08
• 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); Commented May 27, 2016 at 14:23
• p?q.push(i):null; -> p+=p?","+i:""; Commented May 27, 2016 at 14:27
• for(...){} -> for(...); Commented May 28, 2016 at 1:09
• 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); Commented May 28, 2016 at 1:15

# Brachylog, 6 bytes

$!$pd.


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

• $!$pd should save some bytes Commented Jun 22, 2016 at 14:01
• @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. Commented Jun 22, 2016 at 14:16
• The question said prime factorization is allowed. Commented Jun 22, 2016 at 14:18

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


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

# Perl 5, 37 bytes

36, plus 1 for -nE instead of -e

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


Input and output are in unary.

• 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. Commented May 30, 2016 at 3:15

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

# J, 7 bytes

~.@q:@!


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

# 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`