Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

This question already has an answer here:

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.

share|improve this question

marked as duplicate by feersum, Mego, Peter Taylor code-golf Jan 24 at 23:09

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.

5  
@feersum That's most definitely not a duplicate. Your linked question involves time complexity in the scoring system. – Doorknob Jan 24 at 15:26
2  
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 at 15:36
3  
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 at 16:23
3  
@ElliotA. Please edit the question when clarifying. Comments are not permanent. – Mego Jan 24 at 18:03
5  
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 at 23:10

26 Answers 26

up vote 19 down vote accepted

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.
share|improve this answer

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
share|improve this answer
3  
How can you test for primality by regex? – flawr Jan 24 at 15:24
3  
@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. – VTCAKAVSMoACE Jan 24 at 15:27
4  
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. – Camil Staps Jan 24 at 21:52
1  
@CamilStaps Thanks - this is my standard Java primality testing code, I forgot to remove that bit of the test. :P – VTCAKAVSMoACE Jan 24 at 21:55
1  
By the way, this seems just like your challenge :) – Camil Staps Jan 24 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++);}
share|improve this answer
1  
Perhaps is not a small-sized program, but by far the most neat :) – xjose97x Jan 24 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 at 17:19
    
Thanks @Dennis, will shorten the code :). Was not aware of that. – xjose97x Jan 24 at 17:23
    
I cutted some whitespaces off and reduced names. Here should be the same program but with 218 bytes, pastebin.com/jysj1uTT. – TuukkaX Jan 24 at 17:25
    
Thanks @TuukkaX, that really was an improvement. – xjose97x Jan 24 at 17:27

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.

share|improve this answer

MATL, 16 bytes

2iq:"t`Qtt:\~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
share|improve this answer

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.

share|improve this answer

Haskell, 46 bytes

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

Using @Mauris'/@xnor's prime checker.

share|improve this answer
1  
Computing the primes list and factorial iteratively gave the same length k%p=[k|p`mod`k>0]++(k+1)%(p*k*k)\n(`take`(1%1)). – xnor Jan 24 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)
share|improve this answer
    
(2..$n).grep({!(2..$_.sqrt.Int).grep($_%%*)}) #45 bytes but less comparissons – Matt Oates Jan 25 at 13:12
1  
@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 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).

share|improve this answer
1  
Oh nice, this is the first time I've seen Chapel here. It's a pretty neat language. – Alex A. Jan 24 at 20:40

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)));}}
share|improve this answer

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
share|improve this answer

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!

share|improve this answer

Pyth - 13 bytes

Wilson's Theorem

j.f!%h.!tZZQ2

Test Suite.

share|improve this answer
3  
You don't need the j any more. – FryAmTheEggman Jan 24 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.

share|improve this answer

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)
share|improve this answer

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
share|improve this answer

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.

share|improve this answer

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:  http://codegolf.stackexchange.com/q/70001/2338
// My answer: http://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);}
share|improve this answer

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]
share|improve this answer
1  
According to out defaults for I/O, you cannot assume that the input is stored in a variable. – Dennis Jan 24 at 18:14
1  
@Dennis Now the input comes from the argument of a function. – Bob Jan 24 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 at 18:32
    
@Dennis OK, thanks. Then it is back to 72 bytes. – Bob Jan 24 at 18:34

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

share|improve this answer

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

share|improve this answer

C#, 316 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)
    {
        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;
    }

Takes the input from STDIN and prints N primes, each to a new line.

Couple tricks used here are ~(2 << 30), shortened way of saying 2147483647. True and false words have been replaced with 0<1 and 1<0, they'll evaluate accordingly.

share|improve this answer

Japt, 23 bytes

U+1 ²o f_o2 eY{Z%Y}} ¯U

Test it online!

share|improve this answer

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));
share|improve this answer

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

share|improve this answer

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.

share|improve this answer
    
That isn't ES5. – Mama Fun Roll Jan 24 at 22:52
    
Assuming you meant ES6, !p.some(c=>!(i%c)) perhaps? – Neil Jan 24 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 at 9:46

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