Fredagsoppgave (finn primtall)

[tvangsgreie]

Lag et Perl-script som finner primtall. Det er lov å jukse for 2. Mitt bruker 2.08 sekunder på å finne alle opp til 100000 og 35,8 sek opp til 1 mill på en Celeron 366, noen bedre? Du kan ta tiden med "time ./script.pl" om du bruker et UNIX-kompatibelt OS.

Endret 12. november 2004 av tvangsgreie

[Torbjørn]

en noe urafinert metode gir 3.14 sek på en 1 GHz P3 maskin med 384 mb ram:

 

echo 100000|time perl -e '$n=<> or die "no number?";MAIN:for($i=5;$i<$n;$i+=2){$r=sqrt($i);$j=3;do{ next MAIN unless $i%$j++} until $j>$r;print $i,",";}' > /dev/null

 

77 sek på 1 mill.

 

kan sikkert rafineres med en index, men da blir minnebruk en issue.

 

hva gir den koden på ditt system?

[Torbjørn]

hva var koden du brukte? og hvor fort kjører kodesnutten min på ditt system?

[tvangsgreie]

Beklager, glemte det bort Her er min kode:

#!/usr/bin/perl

my @primes = (2);
CANDIDATE: for (my $a=3;$a<1000000;$a+=2) {
   my $max = sqrt($a);
   foreach my $prime (@primes) {
       next CANDIDATE if (! ($a % $prime));
       last if ($prime > $max);
   }
   push @primes, $a;
}
print join(", ", @primes) . "\n";

Den bruker ganske riktig en indeks, men den blir egentlig ikke spesielt stor.

 

Koden din brukte 2 min 52 sek på Celeronen min. Perl er desverre ikke spesielt raskt, så det lønner seg vanligvis å ha minst mulig kalkulering/looping, og i stedet bruke de underliggende datastrukturene.

[Torbjørn]

hvor ble det av python svaret? Jeg syntes det var et bra bidrag til tråden. representerte andre ytterpunktet i forhold til min løsning. idet den lager en n elementer stor indeksarray og puncher ut alle tall fra den som er en faktor av et annet tall

[superlaban]

Beklager, glemte det bort Her er min kode:

my @primes = (2);
CANDIDATE: for (my $a=3;$a<1000000;$a+=2) {
   my $max = sqrt($a);
   foreach my $prime (@primes) {
       next CANDIDATE if (! ($a % $prime));
       last if ($prime > $max);
   }
   push @primes, $a;
}
print join(", ", @primes) . "\n";

Den bruker ganske riktig en indeks, men den blir egentlig ikke spesielt stor. Koden din brukte 2 min 52 sek på Celeronen min. Perl er dessverre ikke spesielt raskt, så det lønner seg vanligvis å ha minst mulig kalkulering/looping, og i stedet bruke de underliggende datastrukturene.

En liten utfordring dette. Jeg justerte din kode litt,

kjørte da ca 7.5% raskere. Slik:

my @primes=(2);
my $a=1;
my $max;
CANDIDATE:
while($a+=2 and $a<1000000 and $max=sqrt($a)){
  for my $p (@primes){
    $a % $p or next CANDIDATE;
    $p>$max and last;
  }
  push @primes, $a;
}
#print join(", ", @smallprimes,@largeprimes) . "\n";

 

Men siden man godtar "juks" på 2, så godtar man det kanskje på

flere av de minste primtallene? På følgende måte (se under) går

det endel raskere. Nær 40%? Man kunne også tenke seg et

perl-program som "omprogrammerte" seg selv (vha eval) etterhvert,

slik at @smallprimes ble initiert til en enda lengre tallrekke.

 

Men selvfølgelig: Et C eller asm-program er å foretrekke

hvis det er SVÆRT mange primtall som skal finnes.

 

 

my @largeprimes;
my @smallprimes=(2,3,5,7,9,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67);
my $zzz=join" and ",map{'$a%'.$_}grep$_>2,@smallprimes;
my $pl=<<'E';$pl=~s/zzz/$zzz/;eval$pl;
my $a=1;
my $max;
CANDIDATE:
while($a+=2 and $a<1000000 and $max=sqrt($a)){
  zzz or next;
  for my $p (@largeprimes){
    $a % $p or next CANDIDATE;
    $p>$max and last;
  }
  push @largeprimes, $a;
}
E
#print join(", ", @smallprimes,@largeprimes) . "\n";

[superlaban]

Og siden jeg liker perl-golf, så burde jeg såklart ha byttet denne:

my $pl=<<'E';$pl=~s/zzz/$zzz/;eval$pl;

Med dette:

$_=<<'E';s/zzz/$zzz/;eval;