Program wybierający liczby mające 18 dzielników

Question

Witajcie. Właśnie próbuję robić zadania do matury z informatyki. Moje zadanie brzmi tak : "Wśród liczb występujących w pliku wejściowym znajdź te, które mają dokładnie 18 dzielników naturalnych (wliczając w nie 1 i samą liczbę)."

Wykombinowałem coś takiego :

#include <iostream>
#include <fstream>
using namespace std;
int main()
{
 ifstream plik;
 plik.open("liczby.txt");
 long liczba,ilosc=0,dzielnik;
 while (!plik.eof())
 {
 	plik>>liczba;
	dzielnik=0;
	ilosc=0;
	do
	{
	   dzielnik++;
 	   if(liczba%dzielnik==0) ilosc++;
    } while (dzielnik==liczba);
	if(ilosc==18) cout<<liczba<<endl;
 }

}

Szkoda tylko, że nie działa :P. Byłbym wdzięczny o wskazówkę :).

Answer 1

Jak obliczyć liczbę dzielników. Iterowanie od 1 do danej liczby jest bez sensu.

Mój algorytm. Najpierw dla liczb,  których pierwiastek€N:

Bierzemy 100. x, czyli pierwiastek jest równy 10.
Sprawdź dzielniki od 1 do 10 więc mamy: 1,2,4,5,10
Sprawdź ile jest dzielników od tych, które powstały.
Mamy: 100, 50, 25, 20 (10 już mamy).
Morał: ilość dzielników liczb, których pierwiastek jest liczbą całkowitą to:

(ilość dzielników z zakresu <1;pierwisatek_liczby>)*2-1;

A jak z liczbami których pierwiastek nie jest całkowity?

Tak samo z małą różnicą: pierwiastek zaokrąglamy w górę. Wtedy:
(ilość dzielników z zakresu <1;pierwisatek_liczby>)*2;

Implementacja algorytmu i jego optymalizacja pod względem szybkości i pamięci dla Ciebie