Numarul de divizori primi ai uni numar

[•AlexAnastasiu]

Salut! As avea o mica problema. Am de aflat divizorii primi ai unui numar in c++ si nu imi dau seama cum sa fac. Iata la ce m-am gandit: fac ciurul pana la numar si aoi numar divizorii primi. Ma puteti ajuta,va rog?

[•TheNechiz]

Ideea ta de rezolvare e bună. Nu înțeleg unde ai probleme. La implementare ?
Poți să rezolvi problema și fără ciur, depinde de cât de optimă vrei să fie rezolvarea.

FARA CIUR:

Cod:

# include <stdio.h>

int main()
{
    int numar,divizor,d,k,prim;

    scanf("%d",&numar);
    k = 0;
    if( numar% 2 == 0 )
    {
        printf("%d ",2);
        k = 1;
    }
    for( divizor = 3 ; divizor <= numar/2 ; divizor += 2 )
    {
        // Incep de la 3. Niciun numar prim nu e par, cu exceptia lui 2.
        prim = 1;
        if( divizor%2 == 0 )
            continue; // Daca divizor nu e prim, merg la urmatorul divizor posibil.
        for( d = 3 ; d <= divizor/2 ; d += 2 )
            if( divizor%d == 0 )
            {
                prim = 0;
                break; // Daca am aflat ca divizor nu e prim, ies din for
            }
        if( prim == 0 )
            continue; // Daca divizor nu e prim, merg la urmatorul divizor posibil.
        if( numar%divizor == 0 )
        {
            printf("%d ",divizor);
            k = 1;
        }
    }
    if( k == 0 )
        puts("Numarul nu are divizori primi proprii.");

    return 0;
}

CIUR:

Cod:

# include <stdio.h>
# define NMax 200001

int V[NMax];

void ciur()
{
    int i,j;

    for( i = 2 ; i <= NMax ; ++i )
        for( j = i+i ; j <= NMax ; j +=i )
            V[j] = 1;
}

int main()
{
    int i,numar,k;

    k = 0;
    ciur();
    scanf("%d",&numar);
    for( i = 2 ; i <= numar/2 ; ++i )
        if( V[i] == 0 && numar%i == 0 )
        {
            printf("%d ",i);
            k = 1;
        }
    if( k == 0 )
        puts("Numarul nu are divizori primi proprii.");
    return 0;
}

Dacă vrei să mai optimizezi....Ciurul lui Eratostene

[•AlexAnastasiu]

Multumesc frumos.