Witam. Muszę napisac program na informatykę, który wypisze mi wszystkie liczby bliźniacze od 1 do 1000000 (milion) (liczby bliźniacze to dwie takie liczby pierwsze, które różnią się od siebie o 2, a liczby pierwsze to liczby, których jedynym dzielnikiem jest 1 i one same. Przykładem takich liczb jest 11 i 13) i nie mam zbytnio pomysłu jak taki program napisać. Mogę prosić o skromną pomoc?
ok ale to są liczby doskonałe a mi chodzi o bliźniacze :/
Może takie coś?
program Blizniacze;
uses
Crt;
function LiczbaPierwsza(const Liczba: Longint): Boolean;
var
i: Longint;
LDzielnikow: Integer;
begin
LDzielnikow := 2;
for i := 2 to Liczba div 2 do
if (Liczba mod i) = 0 then
Inc(LDzielnikow);
LiczbaPierwsza := LDzielnikow = 2;
end;
var
i: Longint;
begin
ClrScr;
for i := 3 to 1000000 do
if (LiczbaPierwsza(i)) and (LiczbaPierwsza(i - 2)) then
Writeln('Liczby: ', i, ' i ', i - 2);
Readln;
end.
Sprawdzanie, czy liczba jest liczbą pierwszą można zrobić w bardziej efektywny sposób :) ale przecież chodziło o sposób, prawda?
No w sumie mozna sporo przyspieszyc:
function LiczbaPierwsza(const Liczba: Longint): Boolean;
var i,j: Longint;
begin
LiczbaPierwsza := false;
i:=2;
j:=trunc(sqrt(liczba)); // policzyc samemu czemu pierwiastek
while i<=j do
begin
if (Liczba mod i) = 0 then exit; // false jest juz powyzej ustawione
Inc(i,1+(i and 1)); // poza 2 odpadaja wszystkie parzyste
end;
LiczbaPierwsza := true;
end;
var i,j,k: Longint;
begin
writeln;
i:=1;
j:=100; // cokolwiek aby tylko roznica na poczatku byla wieksza niz 2
k:=j; // rowniez prawie obojetne
while i<1000000 do
begin
if LiczbaPierwsza(i)then
begin
if i-j=2 then Writeln('Liczby: ', i, ' i ', j);
if i-k=2 then Writeln('Liczby: ', i, ' i ',k); // wykorzystane bedzie tylko raz dla pary (1,3)
k:=j;
j:=i;
end;
inc(i,1+byte(i>2)); // no tu dla i powyzej 3 skaczemy co 2 , bo parzyste odpadaja z natury rzeczy
end;
Readln;
end.
Wiec odpada polowa podczas sprawdzania liczby, czy jest pierwsza (parzyste won), odpada roznica pomiedzy pierwiastkiem a polowa (rzutuje juz przy liczbach wiekszych od 4), odpada podwojne sprawdzanie kazdej liczby (2 ostatnie pierwsze sa zapamietane), no i odpada sprawdzanie kazdej parzystej w petli glownej programu (znow praktycznie polowa odpada) ... Wiec program ma 1/8 obliczen w stosunku do pierwowzoru, ale za to ma troszke wiecej kodu (2 warunki prawie identyczne) i troszke wiecej danych (j,k) ... Cos za cos
Ale, jak napisałem, to ogólna zasada działania. Teraz napiszmy to w asmie żeby było szybciej :P
// a czy ja przecze ? moje tez mozna jeszcze poprawić i oby ktos to zrobił :> [mf]
Ok ludzie wielkie dzięki :) Jesteście super :).
Ale mam jeszcze jedno pytanko. Jak zabezpieczyć program przed wpisaniem błędnych danych (tj. liczbą/cyfrą nie z przydzielonego jej przedziału np. do inteegera wpisać cześć) i program tak aby sam nie wychodził do kodu? Chodzi mi tutaj o tę dyrektywę {$I} i repeat until keypress(k);. Może mi ktoś powiedzieć dokładnie jak to zrobić?
var
e:integer;
s:string;
L:longint;
...
repeat
readln(s);
val(s, L, e)
until (e=0) and (L>0) and (L<1000000);
...