List Prime Numbers [duplicate]

Question

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 code-golf, so the shortest answer in bytes wins.

Answer 1

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.

Answer 2

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

Answer 3

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++);}

Answer 4

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.

Answer 5

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

Answer 6

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.

Answer 7

Haskell, 46 bytes

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

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

Answer 8

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)

Answer 9

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

Answer 10

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)

Answer 11

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)));}}

Answer 12

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

Answer 13

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!

Answer 14

Pyth - 13 bytes

Wilson's Theorem

j.f!%h.!tZZQ2

Test Suite.

Answer 15

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.

Answer 16

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]

Answer 17

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

Answer 18

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.

Answer 19

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);}

Answer 20

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

Answer 21

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

Answer 22

Japt, 23 bytes

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

Test it online!

Answer 23

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

Answer 24

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

Answer 25

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.

Answer 26

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.