Saturday, November 5, 2011

Solution to Project Euler Problem 7 - 10001th prime number

http://projecteuler.net/problem=7
Problem:

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: The 10001 prime number is: 104743

Solution:
#!/usr/bin/perl -w
use strict;
use Math::Complex;
my (@primes,$ulimit,$stop);
$ulimit=1000000;
$stop=10001;
generate_prime();


sub generate_prime {
        my ($i,$j,$prime,$squareroot,$count);
        @primes=(2,3,5,7);
        $count=4;
        #We know only 2 is the even prime numbers, hence skip all even numbers
        for ($i=9;$i<=$ulimit; $i+=2) {
                $prime=0;
                #Divide the number by all the prime numbers less than the square
 root
                $squareroot=sqrt($i);
                foreach $j (@primes) {
                        if ( $j > $squareroot ) {
                                last;
                        }
                        if (($i%$j) == 0) {
                                $prime=1;
                                last;
                        }
                }
                if ($prime == 0 ) {
                        $count+=1;
                        print "$count: $i \n";
                        push(@primes,$i);
                        if($count == $stop ) {
                                print "The $stop prime number is: $i \n";
                                exit(1);
                        }
                }
        }
}


No comments: