[ demig0d @ 27.02.2010. 19:12 ] @
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;
}
[ Mihajlo Cvetanović @ 27.02.2010. 21:19 ] @
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.
[ demig0d @ 28.02.2010. 15:13 ] @
hvala na odgovoru. moracu malo da proucim to Eratostenovo sito...