Project Euler Problem 7

Problem 7

28 December 2001

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.

What is the 10 001st prime number?

Answer: 104743

 

 

Solution in C#

 

using System;

namespace ConsoleApplication1 {
    class Program {
        static bool isPrime(int n) {
            for (int i = 2; i * i <= n; i++) {
                if (n % i == 0) return false;
            }
            return true;
        }

        static void Main(string[] args) {
            int count = 0;
            for (int i = 2; count < 10001; i++) {
                if (isPrime(i)) {
                    count++;
                    Console.WriteLine("{0}: {1}", count, i);
                }
            }
            Console.ReadKey();
        }
    }
}

Solution in Perl

sub isPrime {
 my ($n) = @_;
 for ( my $i = 2 ; $i * $i <= $n ; $i++ ) {
  if ( $n % $i == 0 ) { return 0; }
 }
 return 1;

}

sub problem7 {
 my $count = 0;
 for ( my $i = 2 ; $count < 10001 ; $i++ ) {
  if ( isPrime($i) ) {
   $count++;
   print "$count $i\n";
  }

 }
}

problem7();

Python

def isPrime(n):    
    for i in xrange(2, sqrt(n) + 1):
        if n % i == 0: return 0
    return 1

def problem7():
    count = 0
    i = 2
    while count < 10001:    
        if isPrime(i):
            count += 1
            print count, i        
        i += 1

problem7()

 

Go

func problem7() {
 count := 0
 for i := 2; count < 10001; i++ {
  if isPrime(i) {
   count++
   fmt.Println(count, i)

  }
 }
}

func main() {
 problem7()
}

C++

bool isPrime(int n) {

    for (int i = 2; i * i <= n; i++) {

        if (n % i == 0) return false;

    }

    return true;

}

void problem7() {

    int count = 0;

    for (int i = 2; count < 10001; i++) {

        if (isPrime(i)) {

            count++;

            //cout << count << " " << i << endl; // slow           

            printf("%d %d\n", count, i);

        }

    }

}

Bash

 

function isPrime {
    local n=$1
    local i
    for ((i=2; i*i <= n; i++)); do
        if ((n%i == 0)); then return 1; fi
    done
    return 0
}

function problem7 {
    local count=0
    local i
    for ((i=2; ; i++)); do
        if isPrime $i; then
            ((count++))
            if ((count >= 10001)); then
                echo $i
                break
            fi
        fi
    done
}

problem7

Javascript

function isPrime(n) {
    for (var i = 2; i * i <= n; i++)
        if (n % i == 0) return false;
    return true;
}

function problem7() {
    var count = 0;
    for (var i = 2; ; i++)
        if (isPrime(i)) if (++count >= 10001) return i;
}
problem7()

Racket

 

(define (prime? n)
  (let loop ([i 2])
    (if (<= (* i i) n)     
        (if (= 0 (modulo n i)) #f
            (loop (add1 i)))
        #t)))

(define (problem7)
  (let loop ([i 2][count 0])
    (if (< count 10001)
        (if (prime? i) (loop (add1 i) (add1 count))
            (loop (add1 i) count))
        (display (sub1 i)))))
(problem7)