prime_1000thprime_diff_eq_9000_optimalized.pl

#! /usr/bin/perl
## sill running for hours :)
## must use c...

# Is there a prime wich after the 1000th prime is exactley bigger by
# 8000 / 9000 / 10000 ...?
# 1000th_prime - prime == 8000 / 9000 / 10000 ...;

use strict;
use warnings;

# store already chcked primes, to make algoritm faster
my %primes = ();
sub prime($) {
  my $number = shift;
  return 1 if ($number == 2);
  return 1 if $primes{$number};

  my $d = 2;
  my $sqrt = sqrt($number);

  while (1) {
    return 0 if ($number % $d == 0);

    if ($d < $sqrt) {
      $d++;
    } else {
      return 1;
    }
  }
}

my @res;
my @diff = ();
my $min = 8000;
my $max = 17000;

for (my $i = $min; $i < $max; $i += 1000) {
    push(@diff, $i);
}


# find a prime, call it 1st
my $first = 1;

OUTER: while (1) {
    $first += 2;
    next unless prime($first);
    $primes{$first} = '';

    # find the 1000th prime ($next) to the 1st prime
    my $last = $first;
    my $next = 0;

    while (1) {
        $last += 2;
        next unless prime($last);
        $primes{$last} = '';
        $next++;

        # check the 1000th prime
        if ($next == 1000) {
            # printf("%-40s", "1000th prim after $first = $last");
            my $diff = $last - $first;

            # if it fit, search is over :)
            if (grep {$diff == $_} @diff) {
                print "I FOUND IT! " x 3 . "\n";
                push(@res, "$diff == $first-$last ($next.)\n");
                last;
            }

            # if it's too big, search is over
            elsif ($diff > $diff[-1]) {
                print "diff is too big    $diff\n";
                last OUTER;
            }

            # if it's too small, get a bigger 1st prime!
            else {
                # print "diff is too small  $diff\n";
                last;
            }
        }
    }
}

print "\n" x 2 . join('',@res);