- Joined
- 26 Apr 03
- Moves
- 26771
Originally posted by PalynkaHere's my code:
Still, I did the b being prime and a being odd but it's still slow. I also have a lower bound for a (it has to be at least >-b), which is still excessive but it cuts some possibilities.
Despite this, it still takes a bit more than 100 secs for the <|1000| ones...
use strict; use warnings; use Benchmark;
my $start_time = new Benchmark;
my $max = 1001; #must be an odd number to get odd a_s (a must be odd)
my $max_prime = 100*$max; # guess at max number we will need to test for primality.
my @notaprime = (1,1,(0) x ($max_prime+1)); # primality test array, zero and 1 are not primes
my @prime = (0,0,(0) x ($max_prime + 1)); #speeds up later test
my @poss_bs; # b must be a prime, so we store all possible prime values of b to speed things up
#Sieve of Eratosthenes
my $num_primes = 0;
my $end = int(sqrt($max_prime));
for (my $num = 2; $num <= $max_prime; $num++) {
next if $notaprime[$num];}[/quote]}
$num_primes++;
$prime[$num] = 1;
push (@poss_bs, $num) if $num <= $max;
next if $num > $end;
for (my $this_mult = $num+$num; $this_mult <= $max_prime;[quote]$this_mult+=$num) {
$notaprime[$this_mult] = 1;
my $num_bs = scalar(@poss_bs);
print "$num_primes primes found up to $max_prime, $num_bs possible bs \n";
# now we have set up the primes we can do euler prob 27
my $big_streak = 39; #suppress boring small streaks
my $max_streak = $big_streak;
my ($max_a, $max_b);
for (my $a = -$max; $a <= $max; $a=$a+2) { #loop through odd a values[
foreach my $b (@poss_bs) {[quote]my $n = 0;}
while () {[quote]my $num = abs($n*$n + $a*$n + $b);
last unless $num; # Definitely not prime if 0 or smaller
if ($num > $max_prime) {[quote]#we got the maximum prime we would have to test wrong!
print "eek result $num with n = $n, a = $a, b = $b is too big!!\n";
if ($prime[$num]) {
$n++;} else {
last}[/quote]}
if ($n > $big_streak) {
my $this_streak = $n;}[/quote]}[/quote]}
print "big_streak of $this_streak when a = $a, b = $b \n";
($max_streak, $max_a, $max_b) = ($this_streak, $a, $b) if ($this_streak > $max_streak);
my $end_time = new Benchmark;
print "Biggest streak was $max_streak when a = $max_a, b = $max_b \n";
my $diff = timediff($end_time,$start_time);
print "Time taken was ", timestr($diff, 'all'😉, " seconds";
This is my code, slower than yours. I think it's because I calculate all first 100 values of the equation and then count the first primes.
uppera = 1000;
upperb = 1000;
maxprimes = 100;
x = 0:maxprimes;
rangeb = primes(upperb);
nprimes = 0;
for b = rangeb
for a = -b:2:uppera
y = x.^2+a*x+b;
if sum(y<0)==0;
c=isprime(y);
temp = min(find(c==0))-1;
coords = [a b]';
if temp > nprimes
store = coords;
nprimes = temp;
elseif temp == nprimes
store = [store coords];
end
end
end
end
- Joined
- 26 Apr 03
- Moves
- 26771
Yep, I think that's why its slow too. Why don't you try reformulating it to find A values which work for all values from n=30 *down* as integer solutions to the formula:
a = (prime - b)/n - n. That should give a tiny number of a's to test further. It should be quick because both 'prime' and b have a quite limited range of possible values.
Originally posted by iamatigerI'm too lazy now. 😛
Yep, I think that's why its slow too. Why don't you try reformulating it to find A values which work for all values from n=30 *down* as integer solutions to the formula:
a = (prime - b)/n - n. That should give a tiny number of a's to test further. It should be quick because both 'prime' and b have a quite limited range of possible values.