Primzahlalgorithmus (Allgemeines zu Perl)

format_c

2004-06-22 20:17

User since
2003-08-04
1706 Artikel
HausmeisterIn

Hi,
Ich stehe vor dem leidigen Problem die Primzahlen eines bestimmten Zahlenbereichs (nicht im mathematischen Sinne Zahlenbereich) herauszufinden.

Ich stehe momentan auf dem Schlauch. Kann mir bitte jemand auf die Sprünge helfen?

Gruß Alex

Effizente Linuxshell

[E|B]

2004-06-22 23:20

User since
2003-08-08
2561 Artikel
HausmeisterIn

Es gibt mehrere Möglichkeiten. Der "Sieb des Eratosthenes" ist wohl für kleinere Zahlenbereiche die beste Möglichkeit. Das Prinzip geht wie folgt:

Code: (dl )

2     3     4
4     6     8
6     9     12
8     12    20
10    15    24

=> 5, 7, 11 fehlt
=> Primzahlen

Du addierst zu einer Zahl x immer wieder x. Das selbe machst du mit x+1, x+2,... Die Zahlen, die nicht weggefallen sind, sind Primzahlen.

Ishka hatte mal einen passenden Algo geproggt. Frag ihn doch mal im ICQ, ob er ihn hier posten kann.\n\n

Gruß, Erik!

s))91\&\/\^z->sub{}\(\@new\)=>69\&\/\^z->sub{}\(\@new\)=>124\&\/\^z->sub{}\(\@new\)=>);
$_.=qq~66\&\/\^z->sub{}\(\@new\)=>93~;for(@_=split(/\&\/\^z->sub{}\(\@new\)=>/)){print chr;}

It's not a bug, it's a feature! - [CGI-World.de]

Ronnie

2004-06-22 23:53

User since
2003-08-14
2022 Artikel
BenutzerIn
[default_avatar]

Eine Runde ->Golf<- der Perlmonks zu diesem Thema.\n\n

Ishka

2004-06-23 00:07

User since
2003-08-04
771 Artikel
HausmeisterIn

Aaaaaaalso: Ich will nicht zwei Tonnen Code zusammensammeln und dann posten, also frag ich dich hier erstmal nach ner genaueren Klassifizierung deines Problems:

Für größere Zahlen'bereiche' dh. mehrere aufeinanderfolgende Zahlen auf Primität zu testen, ist das von EB präsentierte Sieb am schnellsten (wobei es reicht das Sieb mit Primzahlen durchzuführen).

dieser Test sollte für alle 'kleinen' Primzahlen verwendet werden. Klein heißt in diesem Fall kleiner als ne Milliarde oder so.

Wenn du von einer Zahl mit über 95% Wahrscheinlichkeit prim haben willst, dann ist ein einfacher Fermattest am schnellsten.

Wenn du ne Zahl mit beliebig großer Wahrscheinlichkeit prim haben willst, dann ist der Miller-Rabin-Test am schnellsten.

Wenn du ne Zahl definitiv prim haben willst, dann ist der AKS bei über 20000bit am schnellsten. Was unter 20000 bit am schnellsten ist, weiß ich nicht genau (müßte nachschauen).

Wenn du einfach nur ne große Primzahl haben willst, aber nicht von einer Zahl wissen willst, ob sie prim ist, dann ist der von EB erwähnte, von mir programmierte Algo am schnellsten.

Alle Angaben ohne Gewähr auf Algorithmen, die ich nicht kenne, sollte aber nicht so viele sein..

ps:
merkt man, daß du damit eins meiner Lieblingsthemen genau erwischt hast?

sub z{if(@_){1while$x[$k=rand 10];t($t=$x[$k]=1)}print map"$z[$x[$_]]$_".($_%3?
"":"\n"),1..9}sub t{$j=0;$x[$_+1]==$t&&($j+=2**$_)for 0..8;z,die"Gewinner $z[$t]
"if grep$_==($j&$_),7,56,73,84,146,273,292,448;z,die"Gleichstand\n"if@x>9&&!grep
!$_,@x}@x=4;@z=qw{. [ (};z$^T&1;while(<>){next if$_>9||$x[$_];t$t=$x[$_]=2;z 1}

steffenw

2004-06-23 01:21

User since
2003-08-15
692 Artikel
BenutzerIn

Verschiedens Algorithmen sind sehr ausführlich im folgenden Buch beschrieben:

Algorithmen mit Perl
von Jon Orwant, Jarkko Hietaniemi, John Macdonald, John McDonald

Broschiert - O'Reilly
Erscheinungsdatum: April 2000
ISBN: 3897211416

ab EUR 8,95 !!! bei Amazon

$SIG{USER} = sub {love 'Perl' or die};

format_c

2004-06-23 01:45

User since
2003-08-04
1706 Artikel
HausmeisterIn

Danke für die Antworten.
Das Sieb von Ehratosthenes war für die Menge an Zahlen und die Größe nicht unbedingt erforderlich. habe das das Prinzip etwas anders verstanden als EB das beschrieben hat aber läuft auf selbe hinaus. Nun ich habe mir dann doch noch, da leider nicht so viel Zeit war eine vielleicht etwas unsichere Methode und langsame zusammengebastelt.

Ich teile die Zahl durch 2 und schaue ob die Zahl durch diese teilbar ist. Wenn nicht dekrementiere ich die geteilte Zahl und prüfe erneut bis sie teilbar ist. Wenn die Zahl dann teilbar ist (was eine Zahl immer spätestens bei 1 ist) und der Teiler ist 1 ist es eine Primzahl.

@Ishka: Der Algo vom Sieb würde mich schon interessieren.

Gruß Alex\n\n

Effizente Linuxshell

esskar

2004-06-23 02:15

User since
2003-08-04
7321 Artikel
ModeratorIn

user image

für kleine Zahlen kannst du noch folgendes nehmen

Code: (dl )

sub isprim
{
   my $unaer = (1 x shift);

   return ($unaer !~ /^(11+)\1+$/);
}

renee

2004-06-23 08:51

User since
2003-08-04
14371 Artikel
ModeratorIn

@format_c: schau mal auf http://www.primzahlen.de . Dort findest Du ein paar Programme (ich glaube in Java); da ist auch ein Programm mit dem Sieb dabei!

OTRS-Erweiterungen (http://feature-addons.de/)
Frankfurt Perlmongers (http://frankfurt.pm/)
--

Unterlagen OTRS-Workshop 2012: http://otrs.perl-services.de/workshop.html
Perl-Entwicklung: http://perl-services.de/

Taulmarill

2004-06-23 11:26

User since
2004-02-19
1750 Artikel
BenutzerIn

user image

es is, glaub ich, noch uz früh am tage. kann mir mal einer erklären wie genau der regex /^(11+)\1+$/ funktioniert?

$_=unpack"B*",~pack"H*",$_ and y&1|0& |#&&print"$_\n"for@.=qw BFA2F7C39139F45F78 0A28104594444504400 0A2F107D54447DE7800 0A2110453444450500 73CF1045138445F4800 0 F3EF2044E3D17DE 8A08A0451412411 F3CF207DF41C79E 820A20451412414 83E93C4513D17D2B

Taulmarill

2004-06-23 11:36

User since
2004-02-19
1750 Artikel
BenutzerIn

user image

ah, jetzt hab ich's, hab's bei perlmonks gefunden

Quote
We match 2 or more ones in succession, in a non-greedy fashion. That means, it'll first try the regex matching "11" in the parens, and if the rest of the regex fails, it'll backtrack and try "111" in the parens, and so on. (sounds like a for loop...)

wichtig dabei ist, dass man nicht wie ich zu blind sein sollte um my $unaer = (1 x shift); zu sehen.

$_=unpack"B*",~pack"H*",$_ and y&1|0& |#&&print"$_\n"for@.=qw BFA2F7C39139F45F78 0A28104594444504400 0A2F107D54447DE7800 0A2110453444450500 73CF1045138445F4800 0 F3EF2044E3D17DE 8A08A0451412411 F3CF207DF41C79E 820A20451412414 83E93C4513D17D2B