[es] - [Zadatak]Problem sa brzinom izvrsavanja programa

demig0d
Zrenjanin

Član broj: 244001
Poruke: 4
*.dynamic.isp.telekom.rs.

Profil

[Zadatak]Problem sa brzinom izvrsavanja programa

^{27.02.2010. u 19:12 - pre 172 meseci}

U zadatku se trazi da se broj rastavi na proizvod prostih cinilaca.
Kada unesem neki veliki broj (na primer 2 miliona), programu treba dosta vremena da se izvrsi.
Kako da svedem izvrsavanje programa na jednu sekundu?

Code:
/*Napisati program koji za uneti broj proverava da li je:
a) pozitivan ili negativan
b) paran ili neparan
c) prost ili nije prost
d) broj rastaviti na proizvod prostih cinilaca */

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int main()
{
    int i,k=0,n,r;
    int operacija;

    printf("Uneti broj:");
    scanf("%d", &n);

    if(n>=0) printf("\nBroj je pozitivan\n");
    else printf("\nBroj je negativan\n");

    if(n%2==0) printf("Broj je paran\n");
    else printf("Broj je neparan\n");

    r=n;
    if(r<0) r*=-1;
    for(i=1; i<=r; i++)
    {
        if(r%i==0) k++;
    }

    if(k<=2) printf("Broj je prost\n");
    else if(k>2) printf("Broj nije prost\n");

    operacija=0;
    for(i=1; i<=r; i++)
    {
       k=0;

        if(r%i==0)
        {

            if(k<2)
            {
                while(r%i==0)
                {
                 r/=i;
                 if(i==1) break;
                 if(operacija>0) printf("*");
                 if(operacija==0 && n<0) printf("-");

                 printf("%i", i);

                 operacija++;

                }
                 k++;
            }

        }

    }

    return 0;
}

Odgovor na temu

Mihajlo Cvetanović
Beograd

Moderator
Član broj: 37636
Poruke: 1249

+96 Profil

Re: [Zadatak]Problem sa brzinom izvrsavanja programa

^{27.02.2010. u 21:19 - pre 172 meseci}

Prvo, odgovor na pitanja C i D može da se traži u jednoj petlji. Drugo, ta petlja ne mora da ide do kranjeg broja, dovoljno je da ide do sqrt(r). Sve preko toga si zapravo već pokrio. Treće, za dodatno poboljšanje algoritma morao bi da praviš Eratostenovo sito, da bi utvrdio koji su prosti brojevi u opsegu od 2 do sqrt(r), i tako preskočio postupak provere deljivosti za sve ostale brojeve.

Odgovor na temu