algorytm w schemacie N-S - sprawdzanie czy liczba jest liczb

0

jak napisać algorytm w schemacie N-S, który sprawdza czy dana liczb jest liczbą pierwszą?

0

Nie wiem co to jest N-S, ale oglnie sprawdzenie czy liczba jest liczbą pierwszą można zrobić tak, że danę liczbę dzielimy modulo (z resztą) zaczynając od 2 do 7 i jeżeli za którymś razem wynik będzie inny niż 0 liczba nie jest liczbą pierwszą (dotyczy to tylko liczb powyżej 7)

0

5040 - czyżby to była liczba pierwsza?

0

inny niż 0 liczba nie jest liczbą pierwszą

Dzięki Dryo... Jasne, że się pomyliłem, miało być:
... jeśli wynik będzie równy 0 liczba to ta nie jest liczbą pierwszą...

Jakiś mój błąd logiczny... Teraz gra 5040 % 2 = 0

0

Fajnie by bylo gdyby ta metoda faktycznie dzialala :) Niestety sprawdza ona tylko czy rozklad danej liczby zawiera ktoras z liczb od 2 do 7 np 121 nie jest liczba pierwsza a ten test odpowie ze jest. Znajdowanie liczb pierwszych jest nieco bardziej skomplikowanym zagadnieniem - polecam Cormena.

0

Aby stwierdzić, czy dana liczba naturalna n większa od 1 jest liczbą pierwszą, wystarczy sprawdzić, czy wśród liczb mniejszych lub równych pierwiastkowi kwadratowemu n znajduje się przynajmniej jeden jej dzielnik rózny od 1, jeśli nie, to liczba n jest liczbą pierwszą.
Jeśli potrzebujesz liczb pierwszych do 40, użyj wzoru Pn=n[2]-n+41, gdzie n[2] to n kwadrat :P
Kolejny wzór to Pn=n[2]-79+1601 - pozwala wyznaczyć liby pierwsze dla n=1,2,3,...79.
Jeśli Ci to nie wystarcza, skorzystaj z sita Eratostenesa. Algorytm przedstawia się tak:
Wypisujemy kolejne liczby naturalne 2,3,4,...n, gdzie n to dowolnie wybrana liczba naturalna. Z wypisanego ciągu liczb będziemy wykreślać te liczby, które nie są liczbami pierwszymi. Liczba 2 jest liczbą pierwszą; zostawiamy ją i z wypisanego ciągu liczb wykreślamy wszystkie jej wielokrotności (ponieważ nie są one liczbami pierwszymi). Kolejną nie skreśloną liczbą pierwszą jest 3; zostawiamy ją i z wypisanego ciągu liczb wykreślamy wszystkie jej wielokrotności. Kolejną nieskreśloną jest 5 - znów zostawiamy 5 i wykreślamy jej wielokrotności. Postępując dalej w ten sposób, z wypisanego na początku ciągu liczb wykreślimy wszystkie liczby nie będące liczbami pierwszymi (niektóre z nich skreślone będą wielokrotnie). Wszystki nie skreślone liczby, to liczby pierwsze. Uwaga: ta metoda pozwala wyznaczyć wszystkie liczby pierwsze nie większe od ustalonej wcześniej n.
Mam nadzieję, że udało mi się jakoś pomóc :]

0

Przepraszam, że ciągnę ten temat, ale to jest jednak ciekawe:).

Spróbujmy do mojej metody dodać pierwiastek kwadratowy i sprawdzić, czy będzie liczbą całkowitą, albo lepiej przeprowadzić najpierw mój test, a później sprawdzać pierwiastki o wykładniku od 2 do 7 i spradzać, czy w którymś z nich pojawi się liczba niecałkowita, jeśli tak to odrzucamy...

//Krecik - poniechaj... Niejedna tęga głowa nad tym myślała i jakoś żadna nie wpadła na taki "rewelacyjnie prosty" sposób. Poczytaj na ten temat zanim się udzielisz... - m.M

0

Jeśli chcecie stworzyć swój algorytm, to przydatny może okazać się fakt, że każdą liczbę parzystą z wyjątkiem liczby 2 można przedstawić jako sumę dwóch liczb pierwszych:
4=2+2; 6=3+3; 8=3+5; 10=5+5; 12=5+7; ...
Jest to tzw. hipoteza Goldbacha. HIPOTEZA.
A tak poza tym, to skoro OD STAROŻYTNOŚĆI szukano wzoru i do dziś nie znaleziono, to ja wam życzę powodzenia :]

0

co to sa pierwiaski o wykladnikach od 2 do 7 ?? mam zreszta wrazenie ze liczba np 1113172331*37 podwazy twoja metode.

0

Moja metoda opiera sie na tym, że każda liczba niepierwsza posiada przynajmniej jeden taki dzielnik, który jest liczbą pierwszą. Polega na:

  1. Wyznaczaniu wszystkich liczb pierwszych do pierwiastka sprawdzanej liczby. Aby wyznaczyć liczby pierwsze kolejne liczby 1, 2, 3 ... az do Sqrt(n) są sprawdzane, czy któraś z wcześniej wyznaczonych liczb pierwszych jest jej dzielnikiem, jak nie to jest to liczba pierwsza

2.Sprawdzenie czy któraś z wyznaczonych liczb piwerwszych jest dzielnikiem n - sprawdznej liczby, jak nie to n jest liczbą pierwszą:

function Pierwsza(n: LongWord): boolean;
var
  i, j, Len: LongWord; //zmienne dla petli oraz dlugosc tablicy LPierwsze
  pierw: boolean; //czy liczba jest pierwsza 
  LPierwsze: array of LongWord; //dynamiczna tablica z liczbami pierwszymi
begin
  Result := true;  //domyślny rezultat
  if n < 4 then Exit;  // 0,1,2,3 od razu uznane za pierwsze

//krok 1.
  SetLength(LPierwsze, 0);
  for i := 2 to Round(Sqrt(n)) do //petla kolejnych liczb od 2 do pierwiastaka z n
  begin
    pierw := true; //I jest domyślnie liczbą pierwszą
    Len := Length(LPierwsze); //określenie ilości wyznaczonych już liczb pierwszych
    j := Len - 1;

    //sprawdzenie czy któraś z liczb pierwszych jest dzielnikiem I (czy I jest liczbą pierwszą)
    while j < High(LongWord) do //petla skacząca po kolejnych liczbach pierwszych w LPierwsze
    begin               // "< High(LongWord)" zastępuje "> -1" mogłoby być też "< LongWord(-1)"
      if (i mod LPierwsze[j]) = 0 then //jeśli jakaś liczba pierwsza jest dzielnikiem I to
      begin
        pierw := false; //I nie jest pierwszą
        Break;  //wyjście z pętli
      end;
      Dec(j);
    end;
    //koniec sprawdzania

    if pierw then //jeżeli I jest pierwszą to dodaj ją do LPierwsze
    begin
      SetLength(LPierwsze, Len + 1);
      LPierwsze[Len] := i;
    end;
  end;

//krok 2. 
  for i := 0 to Length(LPierwsze) - 1 do
    if (n mod LPierwsze[i]) = 0 then
    begin
      Result := false;
      Exit;
    end;
end;

Dodam jescze, że przy wyższych wartościach różnice pomiędzy kolejnymi liczbami pierwszymi są mniejsze

0

Na pewno prostego wzoru nie ma na wyznaczenie liczb pierwszych. Jedyny znany to przedstawione sprawdzanie wszystkich < sqrt(n) (ew. inne opierające się o taką samą metodę).
Co do hipotezy: to jest jak sam napisałeś hipoteza a nie fakt. Ani nie udowodniono prawdziwości ani nie udowodniono nieprawdziwości.
A co do szybkich metod: http://4programmers.net/view.html?id=199#test_rabina
I proponuję odpuśćcie sobie ten temat... Problem rozwiązania chyba już jest. Ew. jeżeli chcecie dyskutować na temat rozwiązań tego problemu, to załóżcie temat w "Nietuzinkowe tematy".

0

Sasik w swojej pierwszej wypowiedzi ma rację... Albo sie wykreśla wielokrotności... Albo mozna jeszcze dzielić przez każdą liczbę nieparzystą zaczynając od połowy podejrzanej liczby w dół aż do 3 (albo od 3 do połowy). Połowa, bo każda powyżej mieści się mniej niż 2 razy a tu chodzi o n-krotność. Do/od 3, bo parzyste poza 2 odrzuca się - to logiczne. To jest algorytm na dobry procek. ten algorytm działa od liczby 7. Można jeszcze dodać duża pamięć: dzielić liczbę nie przez nieparzyste, ale przez wszystkie poprzednie pierwsze (zapamiętane!! duża liczba - duża pamięć). Minus jest taki, że trzeba przejechać cały zakres od połowy w dól (albo od 3 do połowy - obojętne). Druga metoda, to nic innego niż to, co zaproponował Sasik. Tyle że od d**y strony. Od strony podejrzanej o pierwszeństwo liczby, a nie od strony dzielnika.

0
{wersja 1- dos : tp/bp - na dobry procek}
var i,j:longint;
label lab;
begin
  writeln('1 2 3 5 ');
  i:=7;
  repeat
    j:=i div 2;
    if ((j mod 2)=0)then dec(j);
    repeat
      if(i mod j)=0 then goto lab;   {nie pierwsza}
      dec(j,2)
    until j=1;
    write(i,#32);
    lab:
    inc(i,2)
  until i=maxlongint
end.


{wersja 2 - dos - tp/bp - na dobry procek i pamięć- (dysk)}

var i,j:longint;
    f:file of longint;
label lab;
begin
  assign(f,'pierwsze');
  rewrite(f);
  i:=3;
  write(f,i);
  i:=5;
  write(f,i);
  i:=7;
  repeat    
    seek(f,0);
    repeat
      read(f,j);           {teraz idziemy od dołu od 3}
      if(i mod j)=0 then goto lab;   {nie pierwsza}
    until j>=i div 2;
    write(i,#32);
    seek(f,filesize(f));
    write(f,i);
    lab:
    inc(i,2)
  until i=maxlongint;
  close(f)    {bez sensu, bo i tak wcześniej wciśniecie ctrl break}
end.

Chodzi o to, że pierwsza wersja jest szybsza do pewnego momentu, później lepiej odczytywać te dane jednak z pliku. Sam się kiedys w to bawłem. Chybaże macie sporo pamięci... Proponuję zabawić sie i włączyć to na całą nockę... :) Może starczy wam dysku do rana, bo żaden program nie skończy jeszcze pracy. Wiem, co piszę. A co do metody Sasika... Tu nie wykreśla się wielokrotności, tylko sprawdza, czy liczba nie jest wielokrotnością.

0

Nie chciałbym się czepiać, ale czy 0 jest na prawdę liczbą pierwszą ?! :P

0

Nie chciałbym się czepiać, ale czy 0 jest na prawdę liczbą pierwszą ?!

0 nie jest liczbą pierwszą (tak samo jak każda <1), ale mniejsza o szczegóły.

dzielić liczbę nie przez nieparzyste, ale przez wszystkie poprzednie pierwsze

A co ja napisałem !

Jeszcze małe uaktualnienie do mojego algorytmy, mianowicie zapomniałem o tym żeby dzielić liczbe do jego pierwiastka:

function TForm1.Pierwsza(n: LongWord): boolean;
var
  i, j, SqrtI, Len: LongWord;
  pierw: boolean;
  LPierwsze: array of LongWord;
begin
  Result := true;
  if n < 4 then Exit;
  SetLength(LPierwsze, 1);
  LPierwsze[0] := 2;
  for i := 2 to Round(Sqrt(n)) do
  begin
    pierw := true;
    Len := Length(LPierwsze);
    SqrtI := Trunc(Sqrt(i));
    for j := 0 to Len - 1 do
    begin
      if LPierwsze[j] > SqrtI then Break;
        if (i mod LPierwsze[j]) = 0 then
        begin
          pierw := false;
          Break;
        end;
    end;
    if pierw then
    begin
      SetLength(LPierwsze, Len + 1);
      LPierwsze[Len] := i;
    end;
  end;
  for i := 0 to Length(LPierwsze) - 1 do
    if (n mod LPierwsze[i]) = 0 then
    begin
      Result := false;
      Exit;
    end;
end;

//dopisane do piniżej
flabra, nie rzucaj tak słowami na formum bo możesz nie mieć racji. Programuje praktycznie od niecałego roku i problemem liczb pierwszych zainteresowałem sie dopiero po przeczytaniu pierwszego postu tego topicu. I też algorytm budowałem na chłopski rozum a nie przy pomocy jakichkolwiek gotowców, a do tego, że wystarczy dzielić tylko przez wyznaczone pierwsze doszedłem samemu. Więc zanim napiszesz nic nie wnoszący post do tematu zastanów się troche co piszesz. A jak chcesz jakichś błyskotliwych nowości i pomysłów to pójdź za radą Dryobates'a i załórz nowy topic w Nietuzinkowe tematy.

0

Ubrałeś, to co wcześniej napisał Sasik. I nie ważne że ja zacząłem od połowy, a ty od pierwiastka. Algorytm praktycznie jest ten sam. Nie znałem tej zasady, bo sam sobie wymyślałem go wieki temu jako szczyl. Nie szukałem wtedy w książkach, tylko brałem wszystko na zdrowy chłopski rozum. Ale skoro algorytm jest juz odgórnie znany i ustalony, to proponuję zostawić troche miejsca na naprawdę coś odkrywczego. Na przykład na 'Rabina'. Chociaż nie wiem... 25% na to np. że sąsiad jest ojcem mojego dziecka... To znaczy, że co mam mu obić 1/4 tważy profilaktycznie, czy uznać dziecko za jego, czy swoje? :-) Ludzie, przecież komputer to duzy kalkulator. Tu sie liczy no n miejsc po przecinku, a nie trafia z dokładnością do 25% w jedynkę. !! Chociaż algorytm wcale ciekawy ;-)

Co do tego, czy zero jest liczbą pierwszą... Definicja jest taka... podzielna przez jeden i sama siebie... Podziel przez siebie. Jeśli Ci sie uda, to będziesz pierwszy!! :-P

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