Autor |
Beitrag |
harryp
Beiträge: 52
Erhaltene Danke: 9
Win 8.1
Delphi 7, XE8
|
Verfasst: So 30.04.17 21:34
Schönen guten Abend Entwickler,
ich versuche mich grad an der Ermittlung von Circular Primes (ProjectEuler #35, vermutlich wäre permutable primes der bessere Ausdruck gewesen bei deren Forderung, egal).
Bis 1000 ermittelt mein Programm diese Zahlen korrekt. Setze ich als Obergrenze im selben Quellcode jedoch auf 10000 wirfts mir die folgende Fehlermeldung raus: Im Projekt ... ist eine Exception der Klasse $C0000005 mit der Meldung 'access violation at 0x8dffff73: read of address 0x8dffff73' aufgetreten.
Wie kann ich herausfinden, an welcher Stelle es tatsächlich zum Auftreten dieses Fehlers kommt? (Versuche das schon mit überwachten Ausdrücken usw. nachzuvollziehen, ihr kennt aber bestimmt eine effiziente Variante den Fehler zu finden)
Mit bestem Dank im Voraus,
harryp
|
|
Mathematiker
Beiträge: 2622
Erhaltene Danke: 1447
Win 7, 8.1, 10
Delphi 5, 7, 10.1
|
Verfasst: So 30.04.17 21:41
Hallo,
es gibt nur die zirkularen Primzahlen
11, 13, 17, 37, 79, 113, 197, 199, 337, 1193, 3779, 11939, 19937, 193939, 199933
bis 10^24, außer den Repunit-Primzahlen natürlich.
Ein Quelltext würde bei der Fehlereingrenzung helfen.
Beste Grüße
Steffen
_________________ Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein
|
|
harryp
Beiträge: 52
Erhaltene Danke: 9
Win 8.1
Delphi 7, XE8
|
Verfasst: So 30.04.17 21:54
Ich weiß, nichtsdestotrotz möchte ich dass mein Programm die Zahlen ermittelt (und wie geschrieben, meint es wohl eher permutierbare(?) Primzahlen, hab es nur nach der originalen Aufgabenstellung weiterhin "circular primes" genannt - das Programm wird mittelfristig einfach beide Sorten berechnen).
Natürlich sende ich gern den Quellcode dazu.
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32: 33: 34: 35: 36: 37: 38: 39: 40: 41: 42: 43: 44: 45: 46: 47: 48: 49: 50: 51: 52: 53: 54: 55: 56: 57: 58: 59: 60: 61: 62: 63: 64: 65: 66: 67: 68: 69: 70: 71: 72: 73: 74: 75: 76: 77: 78: 79: 80: 81: 82: 83: 84: 85: 86: 87: 88: 89: 90: 91: 92: 93: 94: 95: 96: 97: 98: 99: 100: 101: 102: 103: 104: 105: 106: 107: 108: 109: 110: 111: 112: 113: 114: 115: 116: 117: 118: 119: 120: 121: 122: 123: 124: 125: 126: 127: 128: 129: 130: 131: 132: 133: 134: 135: 136: 137: 138: 139: 140: 141: 142: 143: 144: 145: 146: 147: 148: 149: 150: 151: 152: 153: 154: 155: 156: 157: 158: 159: 160: 161: 162: 163: 164: 165: 166: 167: 168: 169: 170: 171: 172: 173: 174: 175: 176: 177: 178: 179: 180: 181: 182: 183: 184: 185: 186: 187: 188: 189: 190: 191: 192: 193: 194: 195: 196: 197: 198: 199: 200: 201: 202: 203: 204: 205: 206: 207: 208: 209: 210: 211: 212: 213: 214: 215: 216: 217: 218: 219: 220: 221:
| unit main;
interface
uses Winapi.Windows, Winapi.Messages, System.SysUtils, System.Variants, System.Classes, Vcl.Graphics, Vcl.Controls, Vcl.Forms, Vcl.Dialogs, Vcl.StdCtrls;
type StrFeld = array of String; TForm1 = class(TForm) Memo1: TMemo; Button1: TButton; Button2: TButton; Label1: TLabel; ListBox1: TListBox; procedure Button2Click(Sender: TObject); procedure Button1Click(Sender: TObject); function IstElement(zahl: integer):integer; function Permutationen(zk: String):StrFeld; function Fakultaet(zahl: integer):integer; private procedure Loeschen(zahl: integer); overload; procedure Loeschen(feld: StrFeld); overload; public end;
var Form1: TForm1; cprimes: array of integer; implementation
{$R *.dfm}
procedure TForm1.Button1Click(Sender: TObject); var max: integer; i,j: integer; eratosthenes: array of boolean; testzahlen: StrFeld; als_zk: String; begin max := 100; SetLength(eratosthenes,0); SetLength(testzahlen,0); SetLength(cprimes,0);
SetLength(eratosthenes, max+1); for i := 2 to max do eratosthenes[i] := true;
i := 2; repeat j := i; repeat j := j + i; eratosthenes[j] := false; until j>max; repeat i := i + 1; until eratosthenes[i] = true; until i*i>max;
SetLength(cprimes,101); cprimes[0] := 0;
for i := 2 to max do if eratosthenes[i] then begin cprimes[0] := cprimes[0] + 1; if cprimes[0] >= length(cprimes) then SetLength(cprimes,Length(cprimes)+100); cprimes[cprimes[0]] := i; end;
i := 1; repeat if cprimes[i]>9 then begin als_zk := IntToStr(cprimes[i]); if (pos('2',als_zk)>0) or (pos('4',als_zk)>0) or (pos('5',als_zk)>0) or (pos('6',als_zk)>0) or (pos('8',als_zk)>0) or (pos('0',als_zk)>0) then begin loeschen(cprimes[i]); i:= i-1; end; end; i := i + 1; until i = cprimes[0];
SetLength(cprimes,cprimes[0]+3);
i := 1; repeat testzahlen := Permutationen(IntToStr(cprimes[i]));
for j := 0 to Length(testzahlen)-1 do testzahlen[j] := IntToStr(StrToInt(testzahlen[j]));
for j := 0 to Length(testzahlen)-1 do if IstElement(StrToInt(testzahlen[j]))=-1 then begin Loeschen(testzahlen); Application.ProcessMessages; i := i - 1; break; end;
i := i + 1; until i > cprimes[0];
ListBox1.Items.Clear; for i := 1 to cprimes[0] do ListBox1.Items.Add(IntToStr(cprimes[i]));
Label1.Caption := 'Im Bereich bis '+IntToStr(max)+' existieren '+IntToStr(cprimes[0])+' circular primes.'; end;
procedure TForm1.Button2Click(Sender: TObject); begin close end;
function TForm1.IstElement(zahl: integer):integer; var tmp: integer; i: integer; begin tmp := -1;
for i := 1 to Length(cprimes)-1 do if cprimes[i]=zahl then tmp := i;
IstElement := tmp; end;
procedure TForm1.Loeschen(zahl: integer); var tmp: integer; begin tmp := IstElement(zahl); if tmp > -1 then begin while tmp < Length(cprimes)-2 do begin cprimes[tmp] := cprimes[tmp+1]; tmp := tmp + 1; end; cprimes[0] := cprimes[0]-1; end;
end;
function TForm1.Permutationen(zk: String):StrFeld; var rueckgabe, tmp: StrFeld; i,j,anz: integer; wort: String; begin if length(zk)=1 then begin SetLength(rueckgabe,1); rueckgabe[0] := zk; end else begin tmp := Permutationen(copy(zk,2,Length(zk)-1)); SetLength(rueckgabe,Fakultaet(Length(zk))); anz := 0; for i := 0 to Length(tmp)-1 do for j := 1 to Length(zk) do begin wort := copy(tmp[i],1,j-1); wort := wort + zk[1]; wort := wort + copy(tmp[i],j,Length(tmp[i])); rueckgabe[anz] := wort; anz := anz + 1; end; end;
Permutationen := rueckgabe; end;
function TForm1.Fakultaet(zahl: integer):integer; var rueckgabe,i: integer; begin rueckgabe := 1; for i := 1 to zahl do rueckgabe := rueckgabe*i;
Fakultaet := rueckgabe; end;
procedure TForm1.Loeschen(feld: StrFeld); var i: integer; begin for i := 0 to Length(feld)-1 do Loeschen(StrToInt(feld[i]));
end;
end. |
|
|
Mathematiker
Beiträge: 2622
Erhaltene Danke: 1447
Win 7, 8.1, 10
Delphi 5, 7, 10.1
|
Verfasst: So 30.04.17 22:28
Hallo,
ich habe mich jetzt durch den Algorithmus gekämpft und gestehe, dass ich ihnen noch nicht verstanden habe.
Soviel aber schon: Selbst bei max = 100000 kommt bei mir keine Fehlermeldung (Delphi 7).
Aber er rechnet auch nur bis 1000 die Zahlen aus. Die darüber liegenden Zahlen werden ignoriert.
Morgen sehe ich mal weiter.
Steffen
_________________ Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein
|
|
mandras
Beiträge: 430
Erhaltene Danke: 107
Win 10
Delphi 6 Prof, Delphi 10.4 Prof
|
Verfasst: So 30.04.17 22:47
Du belegts die Arrays erstmal mit Länge 0
und schreibst dann aber Werte hinein.
Könnte dies das Problem sein?
Ich übersetzte das Programm mit der Compileroption "Bereichsprüfung" ,
da meckerte das Programm gleich im Bereich Primzahlsieb.
LG
Andreas
|
|
harryp
Beiträge: 52
Erhaltene Danke: 9
Win 8.1
Delphi 7, XE8
|
Verfasst: So 30.04.17 23:03
mandras hat folgendes geschrieben : | Du belegts die Arrays erstmal mit Länge 0
und schreibst dann aber Werte hinein.
Könnte dies das Problem sein?
|
Wenn ich mich nicht irre, in zwei von drei Fällen sicher nicht (da ich dort vor dem ersten Reinschreiben die Länge wieder erhöhe), beim Feld testzahlen bin ich mir nicht 100%ig sicher wie Delphi agiert, wenn es ein dynamisches Feld als Rückgabewert einer Funktion erhält. Ich habe testweise dort mal jetzt auf 1000 Elemente statt 0 gesetzt, hat aber an der Fehlermeldung nichts geändert.
Aber danke für den Lösungsversuch
Mathematiker hat folgendes geschrieben : | Hallo,
ich habe mich jetzt durch den Algorithmus gekämpft und gestehe, dass ich ihnen noch nicht verstanden habe.
Soviel aber schon: Selbst bei max = 100000 kommt bei mir keine Fehlermeldung (Delphi 7).
Aber er rechnet auch nur bis 1000 die Zahlen aus. Die darüber liegenden Zahlen werden ignoriert.
|
Mein Grundgedanke war folgender:
- Finde alle Primzahlen im fraglichen Bereich raus (-> Sieb des Eratosthenes)
- Lösche alle mehrstelligen Zahlen, die 2, 4, 5, 6, 8 oder 0 enthalten (können bei Permutation dann keine Primzahlen sein)
- Ermittle für alle übrigen Kandidaten einzeln alle Permutationen
- Teste ob es in den Permutationen eine Nicht-Primzahl gibt - ja --> Kandidat löschen
- Was übrig bleibt sollten permutierbare Primzahlen sein
|
|
mandras
Beiträge: 430
Erhaltene Danke: 107
Win 10
Delphi 6 Prof, Delphi 10.4 Prof
|
Verfasst: Mo 01.05.17 01:20
Asche auf mein Haupt!
Du hast Recht, Array erasto setzt Du danach auf Länge <max+1>
Trotzdem meldet das Programm bei mir kurz drauf in der Zeile
eratosthenes[j] := false;
Im Bereich Primzahlsieb einen Bereichsfehler.
|
|
Frühlingsrolle
Ehemaliges Mitglied
Erhaltene Danke: 1
|
Verfasst: Mo 01.05.17 02:28
- Nachträglich durch die Entwickler-Ecke gelöscht -
Für diesen Beitrag haben gedankt: harryp
|
|
harryp
Beiträge: 52
Erhaltene Danke: 9
Win 8.1
Delphi 7, XE8
|
Verfasst: Mo 01.05.17 09:11
Frühlingsrolle hat folgendes geschrieben : | Was könnte an dieser Verschachtelung von repeat-Schleifen nur falsch sein:
...
|
hm, hast Recht; hab's jetzt auf j+i > max abgeändert. Danke für den Hinweis.
Die Fehlermeldung ist erstmal weg.
|
|
Mathematiker
Beiträge: 2622
Erhaltene Danke: 1447
Win 7, 8.1, 10
Delphi 5, 7, 10.1
|
Verfasst: Mo 01.05.17 11:08
Hallo,
mir ist es noch nicht gelungen, die Ursache für die fehlenden Zahlen zu finden.
Vorerst habe ich nur eine alternative Lösung:
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32: 33: 34: 35: 36: 37: 38: 39: 40: 41: 42: 43: 44: 45: 46: 47: 48: 49: 50: 51: 52: 53: 54: 55: 56: 57: 58: 59: 60: 61:
| procedure TForm1.Button3Click(Sender: TObject); var permutationen : tstringlist; zahl : array of boolean; maxx,i,j,s,m,anzahl : integer; unmoeglich:boolean; k:string; begin maxx:=10000000; listbox1.Clear;
setlength(zahl,maxx+1); for i:=1 to maxx do zahl[i]:=true; i:=2; repeat s:=i+i; while s<=maxx do begin zahl[s]:=false; s:=s+i; end; inc(i); while not zahl[i] do inc(i); until i>sqrt(maxx);
permutationen:=tstringlist.create; permutationen.sorted:=true;
for i:=11 to maxx do begin if zahl[i] then begin k:=inttostr(i); unmoeglich:=(pos('0',k)>0) or (pos('2',k)>0) or (pos('4',k)>0) or (pos('5',k)>0) or (pos('6',k)>0) or (pos('8',k)>0); if not unmoeglich then begin permutationen.clear; anzahl:=0; for j:=1 to length(k) do begin k:=k[length(k)]+copy(k,1,length(k)-1); if zahl[strtoint(k)] then begin permutationen.Add(k); inc(anzahl); end; end; if anzahl=length(k) then begin for j:=0 to permutationen.count-1 do begin k:=permutationen[j]; if listbox1.items.indexof(k)<0 then listbox1.Items.add(k); end; end; end; end; end; setlength(zahl,0); permutationen.free; end; |
Schönen 1.Mai
Steffen
_________________ Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein
Für diesen Beitrag haben gedankt: harryp
|
|
Horst_H
Beiträge: 1653
Erhaltene Danke: 243
WIN10,PuppyLinux
FreePascal,Lazarus
|
Verfasst: Di 02.05.17 06:49
Hallo,
Einspruch, Euer Ehren.... ( zuviel Matlock, oder was ?? )
Permutationen sind doch ein paar mehr als: length(k), mehr k!
Delphi-Quelltext 1: 2: 3: 4: 5: 6: 7: 8: 9:
| anzahl:=0; for j:=1 to length(k) do begin k:=k[length(k)]+copy(k,1,length(k)-1); if zahl[strtoint(k)] then begin permutationen.Add(k); inc(anzahl); end; end; |
179 ist ja als Permutationen auch 179,197,719,791,917,971.
Hier wären es nur 179,917,791.
Man könnte die Zahlen aus Ziffern als Kombinationen mit Wiederholung erstellen und dann bei prim die Permutationen testen.
Ala rosettacode.org/wiki...ausen_numbers#Pascal.
Dabei statt ziffer =0..9 nur zifferindex=0..3 und dann Ziffer := cZiffer[Zifferindex] nutzen.
const cZiffer: array [0..3] of integer = (1,3,7,9);
Später mal...
Viel Spaß bei den Abiturprüfungen,
Gruß Horst
EDIT
munchhausen und nicht smith numbers...
|
|
Mathematiker
Beiträge: 2622
Erhaltene Danke: 1447
Win 7, 8.1, 10
Delphi 5, 7, 10.1
|
Verfasst: Di 02.05.17 09:27
Hallo,
Horst_H hat folgendes geschrieben : | Permutationen sind doch ein paar mehr als: length(k), mehr k! |
Du hast soweit recht, dass der Begriff Permutation hier falsch gewählt ist.
Bei den zirkularen Primzahlen werden aber nur die betrachtet, bei denen die hintere Ziffer gestrichen und an den Anfang gestellt wird.
Z.B. bei 197 nur die Zahlen 197 , 719 und 971.
Damit stimmt length(k). Die Bezeichnung "Permutation" ist aber falsch.
Alle Permutationen werden bei permutierbaren Primzahlen betrachtet. Es wäre auch interessant, diese zu ermitteln.
Im Moment fallen mir nur 13, 17, 37, 79, 113, 199, 337 ein.
Beste Grüße
Steffen
_________________ Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein
|
|
Horst_H
Beiträge: 1653
Erhaltene Danke: 243
WIN10,PuppyLinux
FreePascal,Lazarus
|
Verfasst: Mi 03.05.17 10:23
Hallo,
ich habe es mal mit dem ZiffernIndex gemacht und bis 1E9 finde ich auch nichts Neues
2 und 5 fehlen dabei.
Die Siebzeit ist bei weitem das zeitaufwändigste mit 1.926s
Da nur 4 Ziffern (1,3,7,9) benutzt werden können, habe ich einen Zähler mit Basis 4 benutzt, aus dem die Zahl generiert wird.
Bei 9 Ziffern sind es statt 10^9 Zahlen nur 4^9 Zahlen = 262144, was eine enorme Einsparung ist.
Die Rotation der Ziffern um eine Stelle berechne ich, indem ich die unterste Stelle per mod bestimme, die gesamte Zahl durch Division um eine Stelle nach rechts verschiebe und anschliessend mit passender Zehnerpotenz die unterste Ziffer nach oben bewege.
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32: 33: 34: 35: 36: 37: 38: 39: 40: 41: 42: 43: 44: 45: 46: 47: 48: 49: 50: 51: 52: 53: 54: 55: 56: 57: 58: 59: 60: 61: 62: 63: 64: 65: 66: 67: 68: 69: 70: 71: 72: 73: 74: 75: 76: 77: 78: 79: 80: 81: 82: 83: 84: 85: 86: 87: 88: 89: 90: 91: 92: 93: 94: 95: 96: 97: 98: 99: 100: 101: 102: 103: 104: 105: 106: 107: 108: 109: 110: 111: 112: 113: 114: 115: 116: 117: 118: 119: 120: 121: 122: 123: 124: 125: 126: 127: 128: 129: 130: 131: 132: 133: 134: 135: 136: 137: 138: 139: 140: 141: 142: 143: 144: 145: 146: 147: 148: 149: 150: 151: 152: 153: 154: 155: 156: 157: 158: 159: 160: 161: 162: 163: 164: 165: 166: 167: 168: 169: 170: 171: 172: 173: 174: 175: 176: 177: 178: 179: 180: 181: 182: 183:
| {$IFDEF FPC}{$MODE Delphi}{$ELSE}{$APPTYPE CONSOLE}{$ENDIF} uses sysutils;
const base = 4; maxDigits = base-1; cDigits : array[0..base-1] of NativeInt = (1,3,7,9); cMaxPr = 1000*1000*1000; type tDigits =array [0..2+3+3] of longInt; tprimes = array of boolean; var Digits :tDigits;
function BuildWheel(var primes:tprimes;elemAnz:LongInt): longInt; var wheelprimes :array[0..13] of byte; wheelSize,wpno, pr,pw,i, k: LongWord; begin pr := 1; primes[1]:= true; WheelSize := 1;
wpno := 0; repeat inc(pr); pw := pr; if pw > wheelsize then dec(pw,wheelsize); If Primes[pw] then begin k := WheelSize+1; for i := 1 to pr-1 do begin inc(k,WheelSize); if k<elemAnz then move(primes[1],primes[k-WheelSize],WheelSize) else begin move(primes[1],primes[k-WheelSize],elemAnz-WheelSize*i); break; end; end; dec(k); IF k > elemAnz then k := elemAnz; wheelPrimes[wpno] := pr; primes[pr] := false;
inc(wpno); WheelSize := k;
i:= pr; i := i*i; while i <= k do begin primes[i] := false; inc(i,pr); end; end; until WheelSize >= elemAnz;
while wpno > 0 do begin dec(wpno); primes[wheelPrimes[wpno]] := true; end; BuildWheel := pr+1; end;
procedure InitPrimes(var primes:tprimes;elemAnz:LongInt); var sieveprime, fakt : LongWord; begin setlength(primes,elemAnz); sieveprime := BuildWheel(primes,elemAnz); repeat if primes[sieveprime] then begin fakt := elemAnz DIV sieveprime; IF fakt < sieveprime then BREAK; repeat primes[sieveprime*fakt] := false; repeat dec(fakt); until primes[fakt]; until fakt < sieveprime; end; inc(sieveprime); until false; primes[1] := false; end;
function circPrime(var pr:tprimes;nr:NativeInt;MaxIdx:NativeInt):boolean; const PowerOf10 :array[0..9] of NativeInt = (1,10,100, 1000,10*1000,100*1000, 1000*1000,10*1000*1000,100*1000*1000, 1000*1000*1000); var i,r : NativeInt;
Begin dec(MaxIdx); i := MaxIdx; result := pr[nr]; while result AND (i > 0) do Begin r := nr MOD 10; nr := nr div 10+r*PowerOf10[MaxIdx]; dec(i); result := result AND pr[nr]; end; if result then begin i := MaxIdx; repeat pr[nr] := false; r := nr MOD 10; nr := nr div 10+r*PowerOf10[MaxIdx]; write(nr:10); dec(i); until i <0; writeln; end; end;
function NextNum(var Dgts:tDigits):boolean; var i,d:NativeInt; Begin i := 0; repeat d := Dgts[i]; inc(d); iF d< base then Begin Dgts[i] := d; break; end; Dgts[i] := 0; inc(i); until i > High(Dgts); result := i <= High(Dgts); end;
var i,nr,idx,maxIdx : LongInt; primes : array of boolean; BEGIN InitPrimes(primes,cMaxPr); For i := Low(Digits) to High(Digits) do Digits[i] := -1;
i := 0; maxIdx := 0; while NextNum(Digits) do Begin while (maxIdx <= High(Digits)) AND (Digits[maxIdx]>=0) do inc(maxIdx); idx := maxIdx-1; nr := 0; repeat nr := nr*10+cDigits[Digits[idx]]; dec(idx) until idx < 0; CircPrime(primes,nr,MaxIdx); end; writeln(i); END. |
Die Ausgabe ist dann:
Quelltext 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23:
| sh-4.3# time ./CircPrime 3 7 11 11 13 31 17 71 37 73 79 97 113 311 131 197 719 971 199 919 991 337 733 373 1193 3119 9311 1931 3779 9377 7937 7793 11939 91193 39119 93911 19391 19937 71993 37199 93719 99371 193939 919393 391939 939193 393919 939391 199933 319993 331999 933199 993319 999331 17
real 0m1.947s user 0m1.893s sys 0m0.050s |
Gruß Horst
Für diesen Beitrag haben gedankt: Mathematiker
|
|
|