22
\$\begingroup\$

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.

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

26 Answers 26

20
\$\begingroup\$

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.
\$\endgroup\$
0
16
\$\begingroup\$

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
\$\endgroup\$
9
  • 4
    \$\begingroup\$ How can you test for primality by regex? \$\endgroup\$
    – flawr
    Commented Jan 24, 2016 at 15:24
  • 3
    \$\begingroup\$ @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. \$\endgroup\$ Commented Jan 24, 2016 at 15:27
  • 5
    \$\begingroup\$ 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. \$\endgroup\$
    – user42682
    Commented Jan 24, 2016 at 21:52
  • 1
    \$\begingroup\$ @CamilStaps Thanks - this is my standard Java primality testing code, I forgot to remove that bit of the test. :P \$\endgroup\$ Commented Jan 24, 2016 at 21:55
  • 1
    \$\begingroup\$ By the way, this seems just like your challenge :) \$\endgroup\$
    – user42682
    Commented Jan 24, 2016 at 23:48
7
\$\begingroup\$

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++);}
\$\endgroup\$
8
  • 1
    \$\begingroup\$ Perhaps is not a small-sized program, but by far the most neat :) \$\endgroup\$
    – xjose97x
    Commented Jan 24, 2016 at 17:19
  • \$\begingroup\$ 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. \$\endgroup\$
    – Dennis
    Commented Jan 24, 2016 at 17:19
  • \$\begingroup\$ Thanks @Dennis, will shorten the code :). Was not aware of that. \$\endgroup\$
    – xjose97x
    Commented Jan 24, 2016 at 17:23
  • 1
    \$\begingroup\$ I cutted some whitespaces off and reduced names. Here should be the same program but with 218 bytes, pastebin.com/jysj1uTT. \$\endgroup\$
    – Yytsi
    Commented Jan 24, 2016 at 17:25
  • \$\begingroup\$ @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. \$\endgroup\$
    – Yytsi
    Commented Jan 24, 2016 at 17:34
6
\$\begingroup\$

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.

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

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
\$\endgroup\$
5
\$\begingroup\$

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.

\$\endgroup\$
4
\$\begingroup\$

Haskell, 46 bytes

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

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

\$\endgroup\$
1
  • 3
    \$\begingroup\$ 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)). \$\endgroup\$
    – xnor
    Commented Jan 24, 2016 at 19:21
4
\$\begingroup\$

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)
\$\endgroup\$
2
  • \$\begingroup\$ (2..$n).grep({!(2..$_.sqrt.Int).grep($_%%*)}) #45 bytes but less comparissons \$\endgroup\$
    – Matt Oates
    Commented Jan 25, 2016 at 13:12
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ Commented Jan 25, 2016 at 16:33
3
\$\begingroup\$

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

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Oh nice, this is the first time I've seen Chapel here. It's a pretty neat language. \$\endgroup\$
    – Alex A.
    Commented Jan 24, 2016 at 20:40
3
\$\begingroup\$

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)
\$\endgroup\$
0
3
\$\begingroup\$

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)));}}
\$\endgroup\$
3
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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!

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

Pyth - 13 bytes

Wilson's Theorem

j.f!%h.!tZZQ2

Test Suite.

\$\endgroup\$
1
  • 3
    \$\begingroup\$ You don't need the j any more. \$\endgroup\$ Commented Jan 24, 2016 at 17:41
2
\$\begingroup\$

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.

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

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

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
\$\endgroup\$
1
\$\begingroup\$

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.

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

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);}
\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$
1
\$\begingroup\$

Japt, 23 bytes

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

Test it online!

\$\endgroup\$
1
\$\begingroup\$

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));
\$\endgroup\$
1
\$\begingroup\$

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

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

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.

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

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

\$\endgroup\$

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