Imprimă pagina - 3 divizorii proprii-improprii

Titlul: 3 divizorii proprii-improprii
Scris de: Simoiu Robert din Decembrie 15, 2009, 13:16:04

Am o problema de genul: sa se gaseasca toate nr. din intervalul [a,b] care sa aiba exact 3 divizori (improprii+proprii). Aceste numere sunt patralele perfecte de numere prime nu?(ex. 25(5^5),49(7^7).. si o idee de rezolvare plz(eu m-am gandit cu ciurul lui eratostene).Ms

Titlul: Răspuns: O intrebare
Scris de: Andrei Grigorean din Decembrie 15, 2009, 13:30:37

Gasesti cel mai mic numar prim mai mare sau egal cu sqrt(a) - fie acesta p1.
Gasesti cel mai mare numar prim mai mic sau egal cu sqrt(b) - fie acesta p2.
Gasesti toate numerele prime din intervalul [p1, p2] si le afisezi patratele.

Titlul: Răspuns: O intrebare
Scris de: Andrei Misarca din Decembrie 15, 2009, 13:32:47

Da, numerele cu 3 divizori sunt patratele numerelor prime. Asta se poate demonstra pe baza faptului ca daca un numar se scrie ca a₁^b₁*a₂^b₂*...*a_n^b_n, atunci numarul de divizori ai numarului respectiv fi (b₁+1)(b₂+1)...(b_n+1). Cum 3 este numar prim, atunci este evident ca numarul dat este patratul unui numar prim.

Titlul: Răspuns: O intrebare
Scris de: Simoiu Robert din Decembrie 15, 2009, 14:09:59

Bun am vazut p1,p2 si acum cum vad eu daca un numar este prim? eu m-am gandit cu ciurul lui e., dar trebuie sa verific divizorii lui 2 in colo, chiar daca radicalii incep de la 100 de exemplu .... e bine asa?

Mai precis

Cod:

program ciur2;
var a,b,i,j,p1,p2:longint;
    v:array[1..1000000] of longint;
    stop:boolean;
 begin
   write('a=');readln(a);
   write('b=');readln(b);
   if sqrt(a)=trunc(sqrt(a)) then
    p1:=trunc(sqrt(a))
   else
    p1:=trunc(sqrt(a))+1;
   p2:=trunc(sqrt(b));
   if p1>p2 then
    stop:=false
   else
    begin
     for i:=2 to p2 do
      for j:=2 to p2 div 2 do
       v[i*j]:=1;
     for i:=p1 to p2 do
      if v[i]=0 then
       begin
        stop:=true;
        write(sqr(i),' ');
       end;
    end;
     if not stop then
     writeln('Nu exista numere cu 3 divizori in intervalul [',a,',',b,']');
    readln;
 end.

[editat de moderator] daca tot stii sa-ti editezi mesajele, nu mai posta consecutiv
Scuze :)

infoarena

infoarena - concursuri, probleme, evaluator, articole => Informatica => Subiect creat de: Simoiu Robert din Decembrie 15, 2009, 13:16:04