I wrote the most processing power consuming script of my life. It's running from last 7 hours, till not completed !!!
What you will know in this script?
A optimized (to best of my knowledge) perl function to generate prime numbers.
Perl module to find square root.
Perl module to find square root.
How to find prime factors for a given number.
How to screw up your CPU :)
Question:
The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?
Solution:
#!/usr/bin/perl -w
use strict;
use Math::Complex;
my (@primes,$ulimit);
$ulimit=600851475143;
generate_prime();
prime_factors($ulimit);
sub prime_factors {
my ($num)=@_;
my (@prime_factors,@sorted);
print "Prime factors of $num are \n";
foreach(@primes) {
if ( $_ > $num ) {
last;
} else {
if ( ($num%$_) == 0 ) {
push(@prime_factors,$_);
}
}
}
@sorted = sort { $a <=> $b } @prime_factors;
print "@sorted \n";
print "The largest prime factor of $num is: $sorted[$#sorted] \n";
}
sub generate_prime {
my ($i,$j,$prime,$squareroot);
@primes=(2,3,5,7); # Initializing known prime numbers
#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;
}
print "$i: $i%$j\n";
if (($i%$j) == 0) {
$prime=1;
last;
}
}
if ($prime == 0 ) {
print "$i \n";
push(@primes,$i);
}
}
print "@primes \n";
open (FH, ">prime-numbers.txt") || die "Cant create prime-numbers.txt $!";
print FH "@primes\n";
my $len=@primes;
print "Total number of prime numbers from 1 to $ulimit= $len \n";
}