Liczby Pierwsze - Pascal

[koparka]

Nie bylo mnie na pewnej lekcji informatyki i nie wiem jak sie rozwiazuje zadania z liczbami pierwszymi. Troche probowalem kombinowac na wlasna reke, ale jakos to czasem nie wychodzi.

Mam napisac prosty program, ktory sprawdza, czy podana liczba jest pierwsza:

 

program abcd;

uses

crt;

var

a,b:integer;

c:boolean;

begin

clrscr;

writeln ('Program sprawdza czy podana liczba jest pierwsza');

writeln ('Podaj liczbe');

readln (a);

c:=false;

for b:=2 to a-1 do

if (a mod B)=0 then c:=true;

case c of

true:writeln ('Liczba nie jest pierwsza');

false:writeln ('Liczba jest pierwsza');

end;

readln;

end.

 

czy moj tok myslenia jest na dobrej drodze? bo ten program niby dziala, ale czasami klamie... :/

pozdrawiam

 

PS. A jak zrobic zeby program wypisal n liczb pierwszych?

[rojmarek]

liczby a i b raczej nie powinny być integer, a jeśli byś już dostał jakąś ujemną to ci sie for pewnie zapętli.

 

 

linia

for b:=2 to a-1 do

zamiast "a-1" mozesz dac "sqrt(a)" i też bedzie dawał poprawne wyniki, tylko ze duzo szybciej

 

 

case c oftrue:false:end;

moze byc, ale ja bym napisał

if c then writeln ('Liczba nie jest pierwsza')else writeln ('Liczba jest pierwsza');

mozesz jeszcze dodac na początku

if (a>=2) then   for b:=2...

to bedzie dobrze wyświetlał dla 0 i 1 (przyjmując ze odczytujemy tylko liczby nieujemne)

 

czyli cały program:

program liczby_pierwsze;var  a,b:longint;begin  readln(a);  if a<0 then a:=a*(-1);  if a>=2 then  begin    for b:=2 to trunc(sqrt(a)) do      if (a mod b)=0 then        begin          writeln('nie jest pierwsza');          exit;        end  end  else    begin      writeln('nie jest pierwsza');      exit;    end;  writeln('jest pierwsza')end.

Edytowane 6 Maja 2005 przez rojmarek

[sector]

moze to ci pomoze

 

http://www.algorytm.cad.pl/Algorithms/61-70/algorithm67.html

[koparka]

juz napisalem (dziala dobrze), wrzucam tutaj, zeby jak ktos szukal to od razu mial.

zamieszczam tez program ktory wypisuje n liczb pierwszych, o ktory tez pytalem:

 

____________________________________________________________________

____________________________________________________________________

 

program sprawdzanie;

uses

crt;

var

a,b:longint;

c:boolean;

begin

clrscr;

writeln ('Podaj liczbe');

readln (a);

if a<0 then writeln ('Podaj liczbe >0');

if a=0 then writeln ('Liczba 0 nie jest pierwsza');

if a=1 then writeln ('Liczba 1 nie jest pierwsza i nie jest zlozona');

if a>1 then

begin

c:=false;

for b:=2 to a-1 do

if (a mod b )=0 then c:=true;

case c of

true:writeln ('Liczba nie jest pierwsza');

false:writeln ('Liczba jest pierwsza');

end;

end;

readln;

end.

 

 

___________________________________________________________________

___________________________________________________________________

 

 

program nliczb;

uses

crt;

var

a,t:integer;

c,d:word;

x:boolean;

tablica:array[1..10000] of word;

begin

clrscr;

writeln('Program wypisuje liczby pierwsze...');

writeln('Ile liczb wypisac?');

readln (a);

if a<0 then writeln ('Nie mozna wypisac ujemnej ilosci liczb pierwszych');

if a=0 then writeln ('Program nie wypisal zadnej liczby pierwszej');

if a=1 then tablica[1]:=2

else

begin

d:=3;

t:=2;

tablica[1]:=2;

tablica[2]:=3;

repeat

x:=true;

for c:=2 to d-1 do

begin

if (d mod c)=0 then x:=false;

end;

c:=2;

if x=true then

begin

writeln('Aktualnie obliczana liczba pierwsza: ',t);

tablica[t]:=d;

t:=t+1;

end;

d:=d+1;

until t-1=a;

end;

clrscr;

for c:=1 to a do

writeln (c:8,'. liczba pierwsza to: ',tablica[c]);

readln;

end.

Edytowane 11 Maja 2005 przez koparka

[rojmarek]

if a<0 then writeln ('Podaj liczbe >0');if a=0 then writeln ('Liczba 0 nie jest pierwsza');if a=1 then writeln ('Liczba 1 nie jest pierwsza i nie jest zlozona');if a>1 thenbegin

moze sie czepiam, ale bardziej matematycznie byloby a>=2,

a złożnośc średnia spadłaby troszke gdybyś zrobił

if a>=2 thenbegin  ...endelse if a<0 then writeln ('Podaj liczbe >0')else if a=0 then writeln ('Liczba 0 nie jest pierwsza')else if a=1 then writeln ('Liczba 1 nie jest pierwsza i nie jest zlozona');

takie tam poprawki, ale kiedyś to może na prawde pomagać... Edytowane 11 Maja 2005 przez rojmarek

[civi]

Zdaje sobie sprawę, że ta rada kompletnie nic Ci nie pomoże ale zobacz:

#include <iostream>#include <cstdlib>using namespace std;typedef unsigned long long ull;const ull Base = 1000000000ULL;bool Witness(ull a, ull n) {  ull d = 1ULL;  int k = 63;  while((n & (1ULL << k)) == 0ULL)    --k;  for(int i=k;i>=0;--i) {    ull x = d;    d = (d*d) % (n+1ULL);    if(d==1ULL && x!=1ULL && x!=n)      return true;    if((n & (1ULL << i)) != 0ULL)      d = (d*a) % (n+1ULL);  }  if(d!=1ULL)    return true;  return false;}bool Miller(ull n, int s) {  for(int j=0;j<s;j++) {    unsigned long long  a = rand();    a = (a % (n-2ULL)) + 1ULL;    if(Witness(a, n-1ULL))      return false;  }  return true;}int main() {  int tc;  ull n;  cin >> tc;  while(tc--) {    cin >> n;    if(Miller(n,10))      cout << "YES" << endl;    else      cout << "NO" << endl;  }  return 0;}

Tylko jest tu troche bałaganu :)