Informatică, întrebare adresată de porecla666, 9 ani în urmă

Subprogramul minDivPrim are un singur parametru, n, prin care primeşte un număr
natural. Subprogramul returnează cel mai mic număr natural care are aceiași divizori primi ca n.

Scrieţi definiţia completă a subprogramului.


^ Problema de mai sus se găsește pe site-ul pbinfo.ro și încerc să iau 100 de puncte, dar mereu îmi spune că depășesc limita de timp și iau doar 80 de puncte. Funcția mea e mai jos; aș dori să știu cum aș putea îmbunătăți viteza programului.

int minDivPrim(long long n)
{
long long i,p=1;
for(i=2;i<=n;i++)
while(n%i==0)
{
n/=i;
if(p%i!=0) p*=i;
}
return p;
}


porecla666: Exemplu: Dacă introduc 75, rezultatul este 15 pentru că 75 și 15 au aceeași divizori primi (adică produsul divizorilor primi ai lui 75 dau 15).

Răspunsuri la întrebare

Răspuns de ionutg38
8
int minDivPrim(int n){ int P = 1, d = 2; while(n > 1){ if(n % d == 0) { P *= d; while(n % d == 0) n /= d; } d ++; if(d*d > n) d = n; } return P; }
Răspuns de express
24
Sursa mea de 100p la minDivPrim. Succes!

int minDivPrim(int n)
{
    int d, fm, nr = 1;
    d=2;
    do
    {
        fm=0;
        while(n%d==0)
        {
            fm=fm+1;
            n=n/d;
        }
        if(fm>0) nr = nr * d;
        d=d+1;
        if(n>1 && d*d>n) nr = nr * n, n=1;
    } while(n>1);
 return nr;
}

Alte întrebări interesante