# Introduction

Prime numbers are simple, right? Well, now you get your chance to find out!

# Challenge

You must write a program or function that takes an input n and outputs the first n prime numbers.

# Example Input and Output

Input: 10
Output: 2,3,5,7,11,13,17,19,23,29

# Rules

1. You must not include any of the following builtin functions:

• A list of prime numbers

• Primality testing

• Next prime

• Prime factorization

• List of divisors

2. Your output must be in a convenient, unambiguous list format.

This is , so the shortest answer in bytes wins.

## marked as duplicate by feersum, Mego♦, Peter Taylor code-golf StackExchange.ready(function() { if (StackExchange.options.isMobile) return; $('.dupe-hammer-message-hover:not(.hover-bound)').each(function() { var$hover = $(this).addClass('hover-bound'),$msg = $hover.siblings('.dupe-hammer-message');$hover.hover( function() { $hover.showInfoMessage('', { messageElement:$msg.clone().show(), transient: false, position: { my: 'bottom left', at: 'top center', offsetTop: -7 }, dismissable: false, relativeToBody: true }); }, function() { StackExchange.helpers.removeMessages(); } ); }); }); Jan 24 '16 at 23:09

• @feersum That's most definitely not a duplicate. Your linked question involves time complexity in the scoring system. – Doorknob Jan 24 '16 at 15:26
• By the way, there is no need to specify rule 1 (it applies by default), and rule 3 is one of the things to avoid when writing challenges. – Dennis Jan 24 '16 at 15:36
• Are built-ins allowed that get you a list of divisors or the prime factorisation? Also, by default input and output in unary or as byte values is allowed. If that's not what you want, you should explicitly say that input and output will be decimal. And you should clarify if n can be 0 or will always be positive. – Martin Ender Jan 24 '16 at 16:23
• @ElliotA. Please edit the question when clarifying. Comments are not permanent. – Mego Jan 24 '16 at 18:03
• I have voted to close as a duplicate of "find the first n composite numbers" because the difference should be a single logical negation in most languages. – Peter Taylor Jan 24 '16 at 23:10

# Jelly, 14 11 bytes

‘²R©’!²%®Oḣ


Uses Wilson's theorem for the primality test. Try it online!

### How it works

‘²R©’!²%®Oḣ     Main link. Input: n

‘               Increment. Yields n + 1.
²              Square. Yields (n + 1)².
R             Range. Yields [1, ..., (n + 1)²].
This range will always contain max(n,2) or more prime numbers.
©            Store the range in the register.
’           Decrement. Yields [0, ..., (n + 1)² - 1].
!          Factorial. Yields [0!, ..., ((n + 1)² - 1)!].
²         Square. Yields [0!², ..., ((n + 1)² - 1)!²].
%®       Mod by the range in the register.
This yields [0!² % 1, ..., ((n + 1)² - 1)!² % (n + 1)²].
By Wilson's theorem this gives 1 for primes and 0 for non-primes.
O      Find the indices of 1's. This yields all prime number in the range.
ḣ     Keep the first n items.


# Java, 116 113 bytes

Saved 3 bytes thanks to @CamilStaps in a regex reduction!

void x(int c){for(int i=2;c>0;i++)if(!new String(new char[i]).matches("(..+?)\\1+")){System.out.println(i);c--;}}

Uses regex to test primality, prints if it is, else, it continues. Call on an instance of your class as .x(10).

Output for x(10):

2
3
5
7
11
13
17
19
23
29
• How can you test for primality by regex? – flawr Jan 24 '16 at 15:24
• @flawr It does division of the number in unary. It's the same thing as testing with a for loop and modulo-ing up to it, essentially. – Addison Crump Jan 24 '16 at 15:27
• Very nice. You can remove the .?| from the regex: since you're already starting with i=2, you don't need to check for 0 and 1. – user42682 Jan 24 '16 at 21:52
• @CamilStaps Thanks - this is my standard Java primality testing code, I forgot to remove that bit of the test. :P – Addison Crump Jan 24 '16 at 21:55
• By the way, this seems just like your challenge :) – user42682 Jan 24 '16 at 23:48

# C, 125 bytes

Most likely I'm not going to win against the Jelly solution haha. Anyway here's my solution in C. It's not commented and it's very compact to reduce the size of the program. 125 bytes.

c,h,i,j;g(n){for(j=2;j*j<=n;j++)if(n%j<1)return 1;return 0;}main(){scanf("%i",&h);for(i=2;c<h;i++)g(i)?:printf("%i ",i,c++);}

• Perhaps is not a small-sized program, but by far the most neat :) – xjose97x Jan 24 '16 at 17:19
• Welcome to Programming Puzzles & Code Golf! According to the rules in our help center, all submissions to a code golf challenge must be golfed. At the very least, you should get rid of the whitespace and shorten your variable names. – Dennis Jan 24 '16 at 17:19
• Thanks @Dennis, will shorten the code :). Was not aware of that. – xjose97x Jan 24 '16 at 17:23
• I cutted some whitespaces off and reduced names. Here should be the same program but with 218 bytes, pastebin.com/jysj1uTT. – Yytsi Jan 24 '16 at 17:25
• @xjose97x No problem :) You could also reduce couple of brackets it seems... If you have one statement inside two brackets, you can throw the brackets away. – Yytsi Jan 24 '16 at 17:34

## Pyth, 12 bytes

.fq2/%LZSZ0Q


This uses trial division to check primality.

.f         Q   find first Q positive integers that satisfy lambda Z:
/     0      the number of zeroes
%LZ         in map modulo-Z-by
SZ       over inclusive range 1 to Z
q2             equals 2


Try it here.

# MATL, 16 bytes

2iq:"tQtt:\~z2>


This uses current release (10.1.0) of the language/compiler.

Try it online!

### Explanation

This uses two nested loops. The outer one produces each prime, and the inner one increases 1 by 1 from latest found prime until the next prime is found.

To test for primality a modulo operation is used: x is prime if computing mod(x,k) for k=1,2,...,x produces no more than two zeros; that is, if only two numbers of the set 1,2,...,x divide x.

2        % push 2 (first prime) to the stack
i        % input number, "n"
q:       % generate vector [1,2,...,n-1]
"        % "for" loop. This runs n-1 times, to find the n-1 primes after 2
t      % duplicate top of the stack, which contains the latest found prime, "p"
% "do...while" loop. This searches for the next prime
Q    % increament top of stack by 1. This is the current candidate for next prime, "x"
t    % duplicate top of the stack (x)
t:   % produce vector [1,2,...,x]
\    % compute mod(x,k) for k=1,2,...,x
~2>  % if that gives more than two zeros: x is not prime: we need another iteration
% implicitly end "do...while" loop
% implicitly end "for" loop
% implicitly display stack contents


## Dyalog APL, 18 bytes

{⍵↑(⊢~∘.×⍨)1↓⍳2*⍵}


Generates a multiplication table from 2 to 2^n. The prime numbers are those that don't occur, so we take the first n of those.

Try it here.

(take[x|x<-[2..],mod(product[1..x-1]^2)x>0])

• Computing the primes list and factorial iteratively gave the same length k%p=[k|pmodk>0]++(k+1)%(p*k*k)\n(take(1%1)). – xnor Jan 24 '16 at 19:21

# Perl 6,  39  37 bytes

{(2..*).grep({![+] $_ X%%2..^$_})[^$_]} # 39 bytes {(2..*).grep({none$_ X%%2..^$_})[^$_]} # 39 bytes
{(2..*).grep({all $_ X%2..^$_})[^$_]} # 37 bytes  Usage: say {(2..*).grep({all$_ X%2..^$_})[^$_]}( 10 );
# (2 3 5 7 11 13 17 19 23 29)

• (2..$n).grep({!(2..$_.sqrt.Int).grep($_%%*)}) #45 bytes but less comparissons – Matt Oates Jan 25 '16 at 13:12 • @MattOates {(2..*).grep({!first$_%%*,(2.. .sqrt)})[^$_]} would be even more efficient. It takes 0.18 secs for 100 primes vs 15.36 secs for what I have above. The most time efficient for 1000 primes I have come up with is {(2,3,5,7...*).grep({!first$_%%*,(3.. .sqrt)})[^$_]} (It's 0.19 sec for 100 primes though) You have to have the limit outside of your generator so that you can reliably generate 10 primes if given the number 10. – Brad Gilbert b2gills Jan 25 '16 at 16:33 ## Chapel, 108 bytes This is the simple trial division method. I tried Wilson's theorem but came up with something slightly longer. var n=0;read(n);var f=0;var q=0;while(f<n){q+=1;for i in 2..q{if(i==q){writeln(q);f+=1;}if(q%i==0){break;}}}  Chapel is a language designed to run on Cray supercomputers, but I installed it on my laptop. I literally downloaded the language and learned how to write the above program in a total of 2 hours. The language has some interesting features, there is a pretty through X in Y minutes page about it. I'm sure there's some list-based features I haven't seen yet which could cut down on my byte count. As a bonus stat, this compiles into a 519858-byte executable (based on wc -c). • Oh nice, this is the first time I've seen Chapel here. It's a pretty neat language. – Alex A. Jan 24 '16 at 20:40 ## Python 2, 60 bytes n=input() k=P=1 while n: if P%k:print k n-=P%k;P*=k*k;k+=1  Same method as here, Wilson's Theorem, computing the factorial-squared iteratively. 54 bytes as a function: f=lambda n,k=1,P=1:n*[0]and P%k*[k]+f(n-P%k,k+1,P*k*k)  ## C#, 207 bytes using s=System.Console;using System.Linq;class P{static void Main(){int n=int.Parse(s.ReadLine());s.Write(string.Join(",",Enumerable.Range(2,n*n).Where(x=>!Enumerable.Range(2,x-2).Any(y=>x%y<1)).Take(n)));}}  # AppleScript (through osascript), 201 158 bytes If you're wondering how I saved that many bytes: I changed it from AppleScript to osascript (AppleScript from the command line) and used the main method equivalent (on run x) to grab arguments at way less bytes. It's back. The most annoyingly verbose yet awesome language that I've used... AppleScript. on run x set b to 1 repeat while x>0 set b to b+1 set c to 1 repeat while c<b set c to c+1 if b mod c=0 then exit end if b=c log c set x to x-1 end end end ## Retina, 43 bytes Byte count assumes ISO 8859-1 encoding. +m^((::+)\2+|:?)1$1:1
)(:+)1
$1¶$1:
:+$ The trailing linefeed is significant. Input and output in unary (input using 1 and output using : but any other two printable ASCII characters would work for the same byte count). Try it online! # Pyth - 13 bytes Wilson's Theorem j.f!%h.!tZZQ2  • You don't need the j any more. – FryAmTheEggman Jan 24 '16 at 17:41 # Befunge 93, 60 bytes &00p1v<_@#0p00:-1g00.:< 210pv>1+: g01<_v# %p01+1:g01::_^#  I didn't feel motivated enough to install Befunge 98 to try and use its features to golf this more, but this works quite well in Befunge 93. Try it here. Interestingly, this method also leaves all non-prime numbers on the stack. It works by the method of trial division. # Python, 72 bytes To avoid while statements, it simply computes all the prime numbers up to 3**n and then it returns only the fist n. It works, but it is extremely slow for n >= 7 because of the 3**n. lambda n:filter(lambda x:all(x%d for d in range(2,x)),range(2,3**n))[:n]  • According to out defaults for I/O, you cannot assume that the input is stored in a variable. – Dennis Jan 24 '16 at 18:14 • @Dennis Now the input comes from the argument of a function. – Bob Jan 24 '16 at 18:29 • Unnamed lambdas are also acceptable, and you don't need the square brackets. lambda n:filter(lambda x:all(x%d for d in range(2,x)),range(2,3**n))[:n] is 9 bytes shorter. – Dennis Jan 24 '16 at 18:32 • @Dennis OK, thanks. Then it is back to 72 bytes. – Bob Jan 24 '16 at 18:34 ## AutoIt, 155 bytes RegEx to the rescue. Func _($n,$i=0,$0=2)
Do
$1='' For$2=1 To $0$1&='1'
Next
$0+=1 ContinueLoop StringRegExp($1,'^(1?|(11+?)\2+)$')$i+=1
MsgBox(0,0,$0-1) Until$i=$n EndFunc  # Pyth, 14 bytes .f!}0m%Zdr2ZQ2  Explanation  - Autoassign Q = eval(input()) .f Q2 - First Q where ... returns True, starting from 2 r2Z - range(2, Z) m%Zd - [Z%d for d in ^] !}0 - 0 not in ^  Try it here. ## Ceylon, 93 bytes void p(Integer n)=>loop(2)(1.plus).filter((c)=>!(2:c-2).any((d)=>c%d<1)).take(n).each(print);  This is a function which takes an Integer n and prints the first n primes, each in one line. Here formatted and with comments: // Print the first n primes. // // Question: https://codegolf.stackexchange.com/q/70001/2338 // My answer: https://codegolf.stackexchange.com/a/70021/2338 void p(Integer n) => // the infinite sequence of integers, starting with 2. loop(2)(1.plus) // filter by primality (using trial division) .filter((c) => ! (2 : c-2).any((d) => c%d < 1) ) // then take the first n elements .take(n) // print each element .each(print);  This uses the same basic prime check as my answer to the "Is this number prime" question (without the special-casing for 1, which is unnecessary here). If a full program is needed, we need to incorporate some input, too. With a command line argument it becomes 138 bytes: shared void run(){loop(2)(1.plus).filter((c)=>!(2:c-2).any((d)=>c%d<1)).take(parseInteger(process.arguments[0]else"")else 0).each(print);}  With reading a line from standard input we get 136 bytes: shared void run(){loop(2)(1.plus).filter((c)=>!(2:c-2).any((d)=>c%d<1)).take(parseInteger(process.readLine()else"")else 0).each(print);}  # Ruby, 75 55 bytes ->n{a=[] t=2 (a<<t if(2...t).all?{|i|t%i!=0} t+=1)while !a[n-1] a}  Works by trial division # Brachylog, 63 bytes :2{h0|[N:X],X+1=Y,('(X-1=:2reI,X%I=0),Xw,@Nw,N-1=:Y:1&;N:Y:1&)}  '(X-1=:2reI,X%I=0) is the part that checks that a number is prime. the rest is basically setting up a recursive predicate that stops after n primes founds (the h0 part). # Japt, 23 bytes U+1 ²o f_o2 eY{Z%Y}} ¯U  Test it online! # Perl 5 - 75 This is actually adapted and golfed from an old perlmonks post. sub p{for(@n=(2..2**20);@p<@_[0]&&push@p,shift@n;){@n=grep{$_%\$p[-1]}@n}@p}


The output is an array containing the prime numbers, so usage can be:

print join(',',p(100));


# 05AB1E, 17 bytes

Uses the same algorithm as Bob's answer. Note that also for this, input greater than 7 will take a while to compute. If you aren't really patient, you can also change the 3 into a 2 in the code.

Code:

3WmGN<!nN%iN}})Z£


Explanation:

3Wm                # 3 ^ input
G         }     # For N in range(1, 3 ^ input)
N<!n           # Compute (N - 1)!²
N%         # mod N
i }      # If 1
N       # Place N onto the stack
)Z£  # Keep the first Z (auto-assigned to input) elements


Uses CP-1252 encoding

# Javascript ES6, 82 67 Bytes

n=>{for(p=[],i=2;n;i++)!p.some(c=>!(i%c))&&p.push(i)&&n--;return p}


Ungolfed version :

n=>{
for(p=[],i=2;n;i++)                   //Loop until n prime found
!p.filter(c=>(i/c|0)==i/c).length //Test if i is not divisible by previous primes
&&
p.push(i)                         // If prime add to the list
&&
n--;                              // If a prime found, one less to find.
return p;                             // Return list of primes
}


Changed the function to detect prime number thanks to @neil output.

• That isn't ES5. – Mama Fun Roll Jan 24 '16 at 22:52
• Assuming you meant ES6, !p.some(c=>!(i%c)) perhaps? – Neil Jan 24 '16 at 22:52
• Sorry, Forgot that arrow function is ES6 only. TIL about array.prototype.some in ES6. Awesome function, will change code for that. – Naouak Jan 25 '16 at 9:46

## C#, 316 315 bytes

using System;class P{static void Main(string[]a){int x=int.Parse(Console.ReadLine()),i=0;List<int>b=G(~(2<<30));for(;i<x;i++)Console.WriteLine(b[i]);}static List<int> G(int n){var p=new List<int>();for(var i=2;i<n;i++){var o=0<1;foreach(var k in p){if(k*k>i)break;if(i%k==0){o=1<0;break;}}if(o)p.Add(i);}return p;}}


'Cleaner' & ungolfed version that shows what's happening.

    static void Main(string[]a)
{
List<int> b=G(~(2 << 30));
for(;i<x;i++)Console.WriteLine(b[i]);
}
static List<int> G(int n)
{
var p = new List<int>();
for(var i=2;i<n;i++)
{
var o = 0<1;
foreach (var k in p)
{
if (k * k > i)
break;
if (i%k==0)
{
o = 1<0;
break;
}
}
if (o)