jak napisać algorytm w schemacie N-S, który sprawdza czy dana liczb jest liczbą pierwszą?
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)
5040 - czyżby to była liczba pierwsza?
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
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.
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 :]
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
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 :]
co to sa pierwiaski o wykladnikach od 2 do 7 ?? mam zreszta wrazenie ze liczba np 1113172331*37 podwazy twoja metode.
Moja metoda opiera sie na tym, że każda liczba niepierwsza posiada przynajmniej jeden taki dzielnik, który jest liczbą pierwszą. Polega na:
- 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
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".
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.
{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ą.
Nie chciałbym się czepiać, ale czy 0 jest na prawdę liczbą pierwszą ?! :P
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.
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