Dzielniki naturalne liczby

Question

Witam, mam do napisania program który zwraca dzielniki naturalne podanej liczby. Oczywiście bardzo prosty program, jednak poniższy kod wykonuje się zbyt wolno, ma ktoś pomysł co należy zrobić aby program wykonywał się szybciej?

#include <cstdlib>
#include <iostream>
#include <conio.h>
 
using namespace std;
 
int main()
{
 int x = 0;
 
cout << "Wprowadz liczbe : ";
 cin >>x;
 
 for(int i=1;i<=x;i++)
 {
 if (x % i ==0) cout << i<<" ";
 }

 getch();
}

 

Answer 1

Mozesz liczyć liczby tylko do pierwiastka z x i podzielić przez x (chyba że jest kwadratem) i zapisać w tablicy

Comments

Jeśli mógłbyś troszkę jaśniej to byłbym wdzięczny, bo jak narazie nie łapie co daje mi liczenie do pierwiastka z liczby.

A jeśli chodzi o zapis do tablicy to potrzebna jest druga pętla, zeby zapisywalo po kolei?

---

Z tego co widzę kolega już odpowiedział bardziej szczegółowo , jednak też napisze tutaj :)

Masz pętle od 2 do pierwiastka z x :

Bierzesz i ( licznik pętli) i jeśli x jest podzielne przez i to wpisujesz i do tablicy

Jeśli x/i != i to wpisujesz także x/i

Co do tablicy to możesz utworzyć tablice na np 10000 elementów w zależności od zakresu liczb i przechowywać w jakiejś zmiennej ostatnie wolne pole , które zwiększają przy wpisaniu czegokolwiek do tablicy

Jeśli chcesz mieć te liczby od najmniejszej do największej to wystarczy że posortujesz tablicę

---

Dzięki wielkie, już załapałem idee.

Answer 2

No po pierwsze to nie musisz sprawdzać jak masz liczbę n, to n razy, a jedynie do jej pierwiastka kwadratowego. Po za tym dużo wydajniej byłoby zamiast sprawdzanie kolejno 2,3,4,5 ... to :

tablica - zbiór dzielników

znajdujesz dzielnik liczby i dodajesz do tablicy,

liczbę dzielisz na dzielnik i otrzymaną wartość przypisujesz do liczby i liczbę przypisujesz do tablicy

i tak do czasu aż liczba będzie równa 1.

Answer 3

Ewentualnie możesz też na początku sprawdzić czy jest podzielna przez 2 to będziesz miał juz dwa razy mniej liczb do sprawdzenia.