Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
#!/usr/bin/perl -l
use strict;
use warnings;
use Term::ProgressBar;
use Memoize;
use DB_File;
tie my %cache => 'DB_File','primecache',O_RDWR|O_CREAT, 0666;
memoize 'it_is_prime', SCALAR_CACHE => [HASH => \%cache];
# Initialising variables
my $max = 600851475143;
my @primes;
# Subroutine that checks prime state
sub it_is_prime{
my $number=$_[0];
if ($number < 2){
return 0;
};
for (my $check = 2; $check * $check <= $number; $check++){
if ($number % $check == 0){
return 0;
};
};
return 1;
};
# Piecing it together, creating a progressbar first
print "Finding all the prime numbers that could be factors of $max\n";
my $progress = Term::ProgressBar->new({name => 'Identifying Primes', count => sqrt($max), remove => 1});
$progress->minor(0);
my $next_update=0;
for (my $number=0;$number * $number <= $max; $number++){
if (it_is_prime($number)){
push (@primes,$number);
};
$next_update = $progress->update($number) if $number >= $next_update;
};
$progress->update(sqrt($max));
print "Finding the largest prime factor of $max\n";
for (my $index=(scalar(@primes)-1);$index>=0;$index--){
if ($max % $primes[$index] == 0){
print "Largest prime factor, $primes[$index]\n";
last;
};
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.