Dzielniki liczby

0

Witam, otóż muszę napisać program, który wczytuje liczbę podaną przez użytkownika 'p', p-ilość dzielników liczby. Program ma wyszukiwać najmniejsza liczbę która posiada co najmniej 'p'dzielników.
Moja liczba musi być w zakresie liczb int. Jeśli takowej nie ma (nie jest w zakresie int lub nie ma tylu dzielników) to stop. Program robi wszystko co ma robić, ale jeśli poda się za dużą liczbę to niestety się zawiesza. Pomoże ktoś. Drugie problem to wykonuje się za długo przy podaniu większej liczby jak to można usprawnić ?

#include <stdio.h>
#include <math.h>
int ile_dzielnikow(int liczba, int licznik)  /*Zliczanie dzielnikow liczby*/
{
    liczba=licznik;
    int dzielnik=0;
    while(licznik>=1)
    {
        if(liczba%licznik==0)
        {
            dzielnik=dzielnik+1;
        }
        licznik--;
    }
    return dzielnik;
}

int main(void)
{
    int p;
    printf("Podaj liczbe:");
    scanf("%d",&p);
    int dzielnik=0;
    int n=1;
    while(n>0)      /*wyszukiwanie kolejnych liczb*/
    {

        dzielnik=ile_dzielnikow(n,n);
        if(dzielnik>=p)         /*jesli ilosc dzielnikow jet rowna p lub wieksza to wypisz liczbe i ilosc dzielnikow*/
        {
            printf("Liczba:%d Ilosc dzielnikow:%d",n,dzielnik);
            break;
        }
        n=n+1;
    }
    if(dzielnik<p)
    {
        printf("BRAK");
    }

    return 0;
}
0

Dla liczby 3 to nie będzie na przykład 1*2*3, dla 4 - 1*2*3*4 etc.?
Z całą pewnością Twoje bruteforce'owe podejście nie jest dobre, podejdź do tego matematycznie.

0

Zdajesz sobie sprawę, co Ty robisz w tym programie? Każdą liczbę naturalną dzielisz przez wszystkie liczby mniejsze lub równe niej.

Bardzo grubo szacując:
32bitowy int to już jest ~ 1 000 000 000 liczb. To oznacza w Twoim programie ok. 1 000 000 000 000 000 000 operacji dzielenia modulo dla wystarczająco dużych p! Twój program się "zawiesza", bo Twój komputer ma ograniczoną szybkość i nie jest w stanie wykonać tylu operacji w czasie kilku minut. Załóżmy, że Twój procesor ma 1 GHz - wykonuje 1 000 000 000 operacji na sekundę i załóżmy, że dzielenie modulo to pojedyncza operacja. 1 000 000 000 000 000 000 operacji wykona się wtedy w 1 000 000 000 sekund, co oznacza ponad 30 lat!

Innymi słowy: albo wymyślisz coś innego niż dzielenie każdej liczby przez każdą liczbę, albo musisz przyjąć, że Twój program będzie działał tylko dla niewielkich p.

1

Ja bym bazował na rozkładzie liczby na czynniki pierwsze, wszystkie dzielniki będą albo nimi albo ich wielokrotnościami. Dodatkowo wynik dzielenia bez reszty też jest dzielnikiem, wiec możesz zatrzymać się na pierwiastku z tej liczby. Dla wszystkiego mniejszego od niego dodajesz 2 do liczby dzielników, a dla niego samego (o ile jest liczbą całkowitą) 1. Dodatkowo sprawdzaj czy badana nie dzieli się czasem przez któryś z mniejszych dzielników pierwszych, celem uniknięcia liczenia po kilka razy tych samych liczb.

edit: sam tylko brutal force do pierwiastka w pythonie3 podał mi w 0.04 s że 2147483648 (największa liczba mieszcząca się do 32 bitowego inta ze znakiem) ma 32 dzielniki

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0