Suma dzielnikow!

pytanie zadane 29 stycznia 2016 w C i C++ przez Memories Obywatel (1,410 p.)

Witam: Mam taki kodzik:

#include<iostream>
#include<cstdlib>
#include<string>
#include <iomanip>
using namespace std;

int main()
{

int liczba,suma=0,ile;

    cin>>ile;
    while(ile--)
    {
        cin>>liczba;
        for(int i=1;i<=liczba;i++)
        {
            if(liczba%i==0)
                suma+=i;
        }
        cout<<suma<<endl;
        suma=0;
    }

return 0;
}

a tu jest zadanko:

Dla zadanej liczby naturalnej należącej do przedziału [1..1000000] wyświetl sumę jej dzielników.

Input

Pierwsza linia określa ilość zestawów danych.

Każdy zestaw danych składa się z jednej liczby naturalnej.

Output

Dla każdego zestawu danych jedna liczba będąca sumą dzielników danej liczby.

Moj program ogolnie działa, ale pokazuje mi "przekroczono limit czasu"

(0.282s<-- limit czasu). Ma ktos moze pomysl jak zoptymalizować ten kod? Moze robie cos nie tak, cos niepotrzebnie, cos zle licze, jakies rady ? Szukalem innych sposobow, ale nic nie wpadlo mi wiecej do glowy, wujek tez nie pomogl ;c
I małe pytanko: gdzie sprawdzic czas wykonania programu ? Korzystam z codeblocksa.

3 odpowiedzi

odpowiedź 29 stycznia 2016 przez C☺ndzi Stary wyjadacz (12,100 p.)

Czy wszystkie #include'y są potrzebne?

komentarz 29 stycznia 2016 przez Memories Obywatel (1,410 p.)

To wydluza dzialanie czas programu? Nie sa, mam je zeby potem sie nie denerwowac.

komentarz 29 stycznia 2016 przez arek01996 Stary wyjadacz (12,100 p.)

Nie wydłuża, program działa tak samo, ale kompilacja trwa minimalnie dłużej.

odpowiedź 29 stycznia 2016 przez Shelvi96 Obywatel (1,440 p.)

Zauważ, że nie musisz sprawdzać liczb od 1 do liczba, pewien przedział można pominąć gdyż z pewnością nie będzie w nim dzielnika liczby liczba, pomyśl jaki to przedział.

komentarz 29 stycznia 2016 przez Memories Obywatel (1,410 p.)

Fajna podpowiedz, dzieki, o to mi chodzi, mysle

komentarz 29 stycznia 2016 przez Memories Obywatel (1,410 p.)
edycja 29 stycznia 2016 przez Memories

Chodzi o 1 i 5 tak ?Ustawie startowo sume na 2, cos sie polepszy mysle

//edit nie, sume musze wtedy zwiekszyc o 1 + liczba

komentarz 29 stycznia 2016 przez Memories Obywatel (1,410 p.)

no dobra, mam cos takiego:

#include<iostream>
#include <iomanip>
using namespace std;

int main()
{

int liczba,suma=0,ile;

    cin>>ile;
    while(ile--)
    {
        cin>>liczba;
        for(int i=2;i<liczba;i++)
        {
            if(liczba%i==0)
                suma+=i;
        }
        cout<<suma+1+liczba<<endl;
        suma=0;
    }

return 0;
}

Dalej pokazuje, ze przekroczylem czas ;/. Chyba, ze to chodzi o inny przedzial co mowil kolega wyzej.

komentarz 29 stycznia 2016 przez Grzyboo Nałogowiec (28,860 p.)

Raczej chodzi o przedział dla liczby x:

(0.5x, x)

Zauważ, że zawsze dzieląc x przez liczbę od pół x do x otrzymamy liczbę z przedziału (1,2), a więc nigdy nie będzie dzielnikiem.

komentarz 29 stycznia 2016 przez Memories Obywatel (1,410 p.)

Wieeec? Lekko nie rozumiem. Mowiac "x" ma pan ma mysli moja "liczba" tak?

komentarz 29 stycznia 2016 przez Grzyboo Nałogowiec (28,860 p.)

tak .

komentarz 30 stycznia 2016 przez Shelvi96 Obywatel (1,440 p.)

Kolejna podpowiedź:
Ten przedział to (1, sqrt(liczba) )

Wieczorkiem podrzucę rozwiązanie jeśli dalej na nie nie wpadniesz :P

komentarz 30 stycznia 2016 przez Shelvi96 Obywatel (1,440 p.)
edycja 30 stycznia 2016 przez Shelvi96

Dla kilku liczb wypisz sobie wszystkie dzielniki, wypisz też dzielniki z tego przedziału, myślę że powinieneś zauważyć co się święci :)

Aha, i uważaj na kwadraty! :P

odpowiedź 29 stycznia 2016 przez Colossus Mądrala (6,410 p.)

for(int i=1;i<=liczba/2;i++)

I jeszcze na koniec trzeba wypisać samą liczbę

komentarz 29 stycznia 2016 przez Memories Obywatel (1,410 p.)

Wpisalem i zle liczy ;p

komentarz 29 stycznia 2016 przez Colossus Mądrala (6,410 p.)

cin>>liczba;
        for(int i=1;i<=liczba/2;i++)
        {
            if(liczba%i==0)
                suma+=i;
        }
        suma+=liczba;
        cout<<suma<<endl;
        suma=0;
    }

komentarz 29 stycznia 2016 przez Memories Obywatel (1,410 p.)

Rozumiem juz o co chodzi, ale dalej wywala, ze za dlugi czas ;/.

komentarz 29 stycznia 2016 przez Colossus Mądrala (6,410 p.)

A to?
cin>>liczba;
        suma++;
        for(int i=2;i<=liczba/2;i++)
        {
            if(liczba%i==0)
            for(int j=i;j<=liczba/i;j++){
                if(liczba%j==0){
                    suma+=j;
                }
            }
        }
        suma+=liczba;
        cout<<suma<<endl;
        suma=0;
    }