Program znajdujący liczby Mersenne'a w przedzale od 1 do a

0

Witam tak jak w temacie mam napisać w Delphi Pascal 7 program wyszukujący liczby Mersenne'a w przedziale od jeden do a. program ma zwracać także czas trwania operacji. Kod ma być optymalny czyli jak najszybciej wykonywać zadanie. Kod ma być także zabezpieczony przed podaniem złych danych przez użytkownika. Macie jakiś pomysł jak to zrobić bo przyznaje że przygodę z Delphi 7 dopiero zaczynam. Z góry wielkie dzięki za pomoc :D

0

A z którym fragmentem polecenia masz konkretnie problem ?

0

Na foru widziałem kilka kodów ale nie wiem który jest najlepszy. Zabezpieczenie kodu spróbowałbym zrobić poleceniem tray. Natomiast zastanawiam się jakich pól użyć do podawania 'a' myślałem o polu edit a do wyświetlania o memo no i oczywiście przycisk pod którego klikniecie przypisze kod programu

0

Na foru widziałem kilka kodów ale nie wiem który jest najlepszy

Aha, czyli nie próbowałeś tego sam napisać?

Zabezpieczenie kodu spróbowałbym zrobić poleceniem tray.

WTF?

Poza tym, skoro ma to działać szybko, to zrób to w konsoli.

0

W konsoli chętnie bym to zrobił ale osoba która mnie o to prosiła chce to w wersji jak to powiedziała okienkowej. Co do obsługi ort! być może pomyliłem nazwe ale jest taka funkcja która odpowiada za obsługę błędów

0

JqLjc

wojtasm91 napisał(a)

(...)w przedziale od jeden do a(...)
A jak wielkie jest a?

0

a jest równe 48 :D
Sprawdzanie zrób ludzkim sposobem, wybierz rozsądne granice a i sprawdź, czy wpisana liczba jest w tym przedziale. Jeżeli nic, to wywala błąd i tyle. Po co ci try?

0

Witam pytanie jak wielkie jest A? Nie wiem bo to nie jest sprecyzowane w związku z czym rodzi się pytanie jaki typ danych dobrać. Z tego co gdzieś tam zdążyłem zerknąć cząstkowo na definicje tych liczb to pasował by tu chyba integer. Na forum jest kod realizujący liczby pierwsze więc jak znajdę nieco czasu to postaram się to napisać choć szef zawala mnie ostatnio robotą a profesor chce programik i tyle. Zastanawiam się też czy do reprezentacji wyników użyć obiektu memo czy ListBox'a bo wydaje mi się że z ListBox'em programy działają nieco szybciej co wy na to? Macie jakiś sprawdzony kod na którym można się posiłkować? Przyznaje że Pascal to nie moja najmocniejsza strona :(

0
 program ExCzyLiczbaPierwsza;
 
{$APPTYPE CONSOLE}
 
uses
  Math, SysUtils;
 
function ND(N: Int64): Int64;
var
  i: Int64;
begin
  if N<2 then  ND := 0  // liczby mniejsze niz 2 nie sa pierwsze
   else
    if N<4 then  ND := N  // liczby 2 i 3 sa pierwsze
     else
      // dla liczb wiekszych rownych 4 sprawdzamy najpierw czy sa podzielne
      // przez 2 i 3
      if (N mod 2=0) then ND := 2
       else
        if (N mod 3=0) then ND := 3
         else
          begin
            ND := N;   i := 1;
            // dopiero pozniej sprawdzamy, czy sa podzielne przez 6*i-1 i 6*i+1
            // podczas, gdy 6*i-1<=czesci calkowitej z pierwiastka kwadratowego
            // badanej liczby
            while 6*i-1<=Int(Power(N, 0.5)) do
             begin
               if N mod(6*i-1)=0 then
                begin
                  ND := 6*i-1;   Break;
                end
                else
                 if N mod(6*i+1)=0 then
                  begin
                    ND := 6*i+1;   Break;
                  end;
 
               // to jest element interfejsu - nie jest niezbedny
               // kiedy dlugo trzeba czekac na wynik, to ten kod pokazuje ile
               // procent dzielnikow juz sprawdzono
               if i mod 1000000=0 then
                 Write( #13, i div 1000000, 'M (',
                        100.0*i/Int(Power(N, 0.5)): 0:1, '%)'#13 );
               Inc(i);
             end
          end;
end;
 
var
  tylko_pierwsze, tylko_ilosc, znak : Char;
  i, ile_pierwszych, iND, M, N : Int64;
  czas, czas_calk : TDateTime;
 
begin
  Writeln( 'Program szuka liczb pierwszych wsrod liczb nieparzystych '
           + 'z podanego zakresu.' );
  repeat
    tylko_pierwsze := #0;
    Write(#13#10#13#10'Podaj poczatek zakresu: ');   Readln(M);
    Write('Podaj koniec zakresu:   ');   Readln(N);
    Write('Pokaz tylko ilosc liczb pierwszych z tego zakresu [t/n]:');
    Readln(tylko_ilosc);
    if UpCase(tylko_ilosc)<>'T' then
     begin
       Write('Pokaz tylko liczby pierwsze [t/n]:');
       Readln(tylko_pierwsze);
     end;
 
    if M mod 2=0 then  M := M + 1;
    czas_calk := Now;   Writeln;   i:=M;   ile_pierwszych := 0;
 
    while i<N do
     begin
       // To ta linijka sprawdza namniejszy dzielnik liczby wiekszy od 1
       // oraz oblicza, ile czas zabralo jego szukanie
       czas := Now;   iND := ND(i);   czas := 86400*(Now - czas);
 
       if iND=i then
        begin
          if UpCase(tylko_ilosc)<>'T' then
            Writeln(i, #9'czas: ', czas:0:3, ' s <--- liczba pierwsza ---');
          ile_pierwszych := ile_pierwszych + 1;
        end
        else
         if (UpCase(tylko_pierwsze)<>'T')and(UpCase(tylko_ilosc)<>'T') then
          Writeln(i, #9'czas: ', czas:0:3, ' s'#9'najmniejszy dzielnik: ', iND);
       i := i + 2;
     end;
 
    czas_calk := 86400*(Now - czas_calk);
    Writeln( #13#10'Ilosc znalezionych liczb pierwszych: ', ile_pierwszych,
             #13#10'Calkowity czas wyszukiwania (z wyswietl.): ', czas_calk:0:3,
             ' s'#13#10'(UWAGA! wyswietlanie bardzo wydluza oczekiwanie na ',
             'wyniki)' );
    Write(#13#10#13#10'Czy rozpoczac nowe wyszukiwanie [T/N]? ');  Readln(znak);
   until UpCase(znak)<>'T';
end.

ten kod znajduje liczby pierwsze. Tylko problem w tym że nie wiem jak odnieść to do liczb Mersenne'a

0

zobacz Liczby pierwsze - szybki algorytm
dla liczb Mersenne'a mam specjalny test,
sprawdzenie do 2^61-1 zajmuje 0,0 sekund

0

kolego chodziło ci o ten kod?

 var
  p, i, n: longword;   //32 bity
  s, n1: int64;      //64 bity

begin
  p:=2;
  n:=3;  // n  = 2^p - 1
  n1:=2; // n1 = 2^(p-1)
         // n1*n może być liczbą doskonałą
  repeat

    s:=4;                   // 1. Lucas-Lehmer test
    for i:=3 to p do        // 2.
      s:=(s*s - 2) mod n;   // 3.
    if (s=0) or (p=2) then  // 4.

       writeln('Mersenne=2^', p:2, '-1=', n:12, ',  perfect number = ', n1*n);
    p+=1;
    n1:=n+1;
    n:=2*n+1;
  until p>31;
end.

Tylko z tego co ja tu widzę to tutaj podajesz mu wszystkie elementy składowe livzby Mersenne'a. Chyba że źle zrozumiałem kod. a ja jako daną wejściową podaje programowi zakres liczb całkowitych od 1 do a. Podaje mu to w postaci posortowanej tablicy

0

czyli n<=a

0

Ok zrobiłem okienko i napisałem fragment kodu który miał uzupełniać tablice t1 liczbami z zakresu od 1 do a niestety nie działa

procedure TForm1.Button1Click(Sender: TObject);
var
i: integer;
a: integer;
t1: array of integer;
t2: array of integer;
begin
a:=StrToInt(Edit1.Text);

for i:=1 to i<=a do
begin
t1[i]:=i;
end;


end;
 

Nadal nie mam pomysłu jak napisać samo sprawdzanie zawartości tablicy. Przyznaje szczeże że od pascala zaczynałem zabawę z programowaniem ale nie ukrywam że nie lubię składni tego języka. Proszę o pomoc :( Druga tablica zadeklarowana w programie miała posłużyć mi do zapisana odszukanych liczb. A następnie zostać wyświetlona w memo1

0

na na grzyba potrzebna tablica t1[] ? prościej przecie "obliczyć" sobie jej zawartość niż sięgać do niej (pod indeksem i masz i)
ale tak na prawdę to jeszcze nie powiedziałeś jaki problem przed tobą stoi.
zgaduję, że chcesz szukać liczb pierwszych Mersenne'a nie większych niż zadane a
jeżeli tak to "dowcipniej" było by wypełnić tę tablicę liczbami M. by później sprawdzić które z nich są liczbami pierwszymi.
(liczba pierwsza M. i liczba M. to nie to samo)

0

Już pisze dokładnie co ma być zadaniem programu. Mamy zakres liczb którego wartością początkową jest 1 a końcową 'a'. Wartość 'a' podaje użytkownik. W tak uzyskanym przedziale program ma odnaleźć wszystkie liczby będące liczbami Mersenne'a. Nie jest sprecyzowany typ danych. Ja myślałem o typie integer. odnalezione liczby mają zostać wyświetlone. Program ma posiadać interfejs graficzny i obsługę błędów. Ma wyświetlać także czas trwania całej operacji

0

wśród liczb Mersenne'a, zdążają się liczby pierwsze. Nazywamy je liczbami pierwszymi Mersennne'a.

0

Z pomocą kolegi Xitami uzyskałem kod:

 uses sysutils;
 
type tTablica = array [1..63] of qword;
 
function mul(a,b,c:qword):qword; // (a*b) mod c
var r:qword;
begin
    r:=0;
    a:=a mod c;
    while b<>0 do begin
        if odd(b) then begin
            r:= r + a;
            if r>=c then 
                r:=r-c;
        end;
        a:= a shl 1; if a>=c then a:=a-c;
        b:= b shr 1;
    end;
    mul:=r;
end;
 
function czypierwsza(p:dword):boolean; // 1 < p < 121
begin
    if      p mod 2=0 then czypierwsza:= p = 2
    else if p mod 3=0 then czypierwsza:= p = 3
    else if p mod 5=0 then czypierwsza:= p = 5
    else if p mod 7=0 then czypierwsza:= p = 7
    else czypierwsza:= true;
end;
 
function policz(a:qword; var t:tTablica):integer;
var n,s:qword; p,i:dword; k:integer;
begin
    k:=0;
    n:=1;
    for p:=2 to 63 do begin
        n:= n + n + 1; 
        if n>a then begin
            policz:=k;
            exit;
        end;
        //for i:=1 to 500000 do s:=s*s;
        if czypierwsza(p) then begin
            s:=4;
            for i:=3 to p do begin
                s:=mul(s,s,n)-2; 
                //s:=(s*s) mod n-2;
                //if s<2 then s:=n-2+s
                //else s:=s-2;
            end;
            if (s=0) or (p=2) then begin
                inc(k);
                t[k]:=n
            end
        end
    end;
    policz:=k
end;
 
var 
    i, n:integer;
    a:qword;
    czas: double;
    t:tTablica;
begin
    readln(a);
    czas:=time();
    n:=policz(a, t);
    czas:=time()-czas;
    for i:=1 to n do
        writeln(t[i]:20);
    writeln('Czas obliczeń: ', czas*24*60*60:0:2, ' sekund.');
end.

W wersji konsolowej wszystko śmiga pięknie. Niestety gdy chciałem przenieść kod pok klawisz w wersji okienkowej programu zaczęły się problemy z typami danych itp. W programie mam pole Edit1 z którego ma zostać pobrana wartość zmiennej 'a' pole memo1 do którego ma trafić wynik działania programu oraz czas wykonania algorytmu. Wszystko ma stać się po kliknięciu na przycisk button1

1 użytkowników online, w tym zalogowanych: 0, gości: 1