iker_primek_keresese_d_tavolsagra.pl

#! /usr/bin/perl
use strict;
use warnings;

# PARAMETEREK
# iker primek keresese kovetkezo feltetellel:
# ket prim 'kitevo'-edik hatvanyon levo kulonbseguk d

my ($d,$kitevo);
# ($d,$kitevo) = (591629402, 3);
($d,$kitevo) = (3662738913.0894148423, 2.1);

#####################################################################
# primitive primkeresesi algoritmus
sub prime($)
{
  my $number = shift;
  return 1 if ($number == 2);

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

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

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

# futo valtozok
my $i = 1;
my ($diff,$prevdiff);
my ($min, $minloc) = ($d, $i);

# nagysagrendekre optimalizalt kozelito ertek O = log(n)
# kezdeti nagysagrend:
my $nagysagrend = int(log($d)/log(10)) - 2;
my $seeker = 2 * (10 ** $nagysagrend);
my $itercount = 0;

FIRST: while($seeker > 1)
{
  # nagysagrenden beluli kereses
  $diff = $prevdiff = undef;

  # legjobb kozelites keresese
  while(!defined($diff) || !defined($prevdiff) || $diff <= $prevdiff )
  {
    $itercount++;
    $i += $seeker;
    $prevdiff = $diff;
    $diff = abs(int($i**$kitevo) - (($i-2)**$kitevo) - $d);
    # legjobb kozelites tarolasa
    if ($min > $diff)
    {
      $min = $diff;
      $minloc = $i;
      last FIRST if $min == 0;
    }

    # debug
    # print "i:$i  c:$seeker \t  m: $diff \t  p: $prevdiff\n";
  }

  # debug msg

  # kovetkezo iteraciohoz korrigalas
  $i -= 2 * $seeker;
  $i = 1 if $i < 0;
  $seeker /= 10;
}

print "iteraciok szama: $itercount\n\n";

# eredmeny
my ($p,$q) = ($minloc - 2, $minloc);

# szoveges valasz es ellenorzes
print "megtalalt szamok: $p es $q\n";
map {print "$_ " . (prime($_) ? 'prim' : 'nem prim') . "\n";} ($p,$q);
$diff = ($q**$kitevo - $p**$kitevo);
# print "$q^$kitevo - $p^$kitevo = $diff\n";
# print "$diff - $d = ".($diff - $d)."\n";