I'm working on a program that, given a number, will solve for it's primacy or factorization.
The program works as intended, but has a huge performance issue with some large numbers. I believe the biggest issue is due to the sheer number of calculations required, since this is more or less a brute force method.
I know that numbers that even numbers (except 2), multiples of prior numbers can be skipped, and there are no prime factors higher than the square root (and thus can abort at that point). However, when I factor in checking for multiples of all prior numbers (not just known factors for the number), performance suffers badly.
Does anyone have suggestions on how to improve efficiency and speed?
My code is as follows:
chomp($num);
my $time_b = time();
my $sqrt = sqrt($num); #$num has no prime factors higher than
my $primes = {}; #it's square root
my $rest = $num;
my $total = 1;
my $tests = 0;
PRIME: for (my $i = 2; $i <= $sqrt;) { #set up the loop, starting at 2
if ($i != 2 && keys %$primes) { #we can skip all even numbers
for (keys %$primes) { #except 2, and multiples of known
if ($i % $_ == 0) { #factors (more could be skipped, but at
$i += 2; #a huge performance hit on big numbers)
next PRIME; #$i is a multiple, try next odd
} #number
}
}
$tests++ unless (exists $primes->{$i}); #unique possible factors actually tested
TEST: {
if ($rest % $i == 0) { #if the number is a factor
$rest /= $i; #update $rest and $total
$total *= $i;
$primes->{$i}++; #add it to the list and increment
#it's power
if ($rest == $i) { #stop checking if $rest = $i
last PRIME;
}
redo TEST; #try this factor again
}
else { #if the number wasn't a factor
$i += $i != 2 ? 2 : 1; #increment to next odd number
next PRIME; #try next possible factor
}
}
}
if ($total != $num) { #because we stopped checking at
my $last = $num / $total; #sqrt($num), $num / $total is a prime
$primes->{$last}++; #and our last factor
}
my $time_e = time();
my $f;
foreach my $factor (sort { $a <=> $b } keys %$primes) { #sort and print the factorization
print $factor;
print "^" . $primes->{$factor}, if ($primes->{$factor} > 1);
print " * ", if (++$f < keys %$primes);
}
print "\n";
print "$tests possible factors checked\n";
print $time_e - $time_b . " seconds";
The program works as intended, but has a huge performance issue with some large numbers. I believe the biggest issue is due to the sheer number of calculations required, since this is more or less a brute force method.
I know that numbers that even numbers (except 2), multiples of prior numbers can be skipped, and there are no prime factors higher than the square root (and thus can abort at that point). However, when I factor in checking for multiples of all prior numbers (not just known factors for the number), performance suffers badly.
Does anyone have suggestions on how to improve efficiency and speed?
My code is as follows:
Code:
my $num = <STDIN>; chomp($num);
my $time_b = time();
my $sqrt = sqrt($num); #$num has no prime factors higher than
my $primes = {}; #it's square root
my $rest = $num;
my $total = 1;
my $tests = 0;
PRIME: for (my $i = 2; $i <= $sqrt;) { #set up the loop, starting at 2
if ($i != 2 && keys %$primes) { #we can skip all even numbers
for (keys %$primes) { #except 2, and multiples of known
if ($i % $_ == 0) { #factors (more could be skipped, but at
$i += 2; #a huge performance hit on big numbers)
next PRIME; #$i is a multiple, try next odd
} #number
}
}
$tests++ unless (exists $primes->{$i}); #unique possible factors actually tested
TEST: {
if ($rest % $i == 0) { #if the number is a factor
$rest /= $i; #update $rest and $total
$total *= $i;
$primes->{$i}++; #add it to the list and increment
#it's power
if ($rest == $i) { #stop checking if $rest = $i
last PRIME;
}
redo TEST; #try this factor again
}
else { #if the number wasn't a factor
$i += $i != 2 ? 2 : 1; #increment to next odd number
next PRIME; #try next possible factor
}
}
}
if ($total != $num) { #because we stopped checking at
my $last = $num / $total; #sqrt($num), $num / $total is a prime
$primes->{$last}++; #and our last factor
}
my $time_e = time();
my $f;
foreach my $factor (sort { $a <=> $b } keys %$primes) { #sort and print the factorization
print $factor;
print "^" . $primes->{$factor}, if ($primes->{$factor} > 1);
print " * ", if (++$f < keys %$primes);
}
print "\n";
print "$tests possible factors checked\n";
print $time_e - $time_b . " seconds";