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

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ę :).

dzielnik=0;
//
dzielnik++;
//
while(dzielnik==liczba);

No ten warunek while to ci spełni tylko 1.

Ok, już rozumiem. Zmieniłem na while(dzielnik!=liczba); i wszystko działa jak należy :D.
Dzięki!

Można nieco przyspieszyć (sprawdzanie czy np. 123 456 789 dzieli się przez 77 145 913 lub przez 123 456 789 jest trochę bez sensu):

dzielnik=1;
ilosc=2;
do
{
    dzielnik++;
    if(liczba%dzielnik==0)
        ilosc++;
 } while (dzielnik<liczba/2);

Dużo większe przyspieszenie można uzyskać tak:

 double epsilon = 0.0000001;
 ...
 dzielnik=1;
 ilosc=2;
 root = long(sqrt(liczba));
 
 if(fabs(liczba - root*root) < epsilon)
 {
     ilosc++;
 }
 do
 {
       dzielnik++;
       if(liczba%dzielnik==0)
       {
           ilosc+=2;
       }
 } while (dzielnik<sqrt(liczba) - 1);

@bogdans, o smrodku przy inkrementacji już wiesz: http://4programmers.net/Forum/1101404

1. liczba powinna być całkowita, root przekonwertowałeś do long, więc jakim cudem spodziewasz się w wyrażeniu liczba-root*root wyniku na poziomie 1E-7 ?
2. Obliczenie na każdym kroku pętli sqrt(liczba) - 1 - to może zjeść cały zysk
3. Użycie do jest strasznie naciągane w tych kodach
4. Obie wersji działają niepoprawnie, zastanów się co zwrócą twoi algorytmy dla liczby: 2, 4, 12, 15, 20 itp.
   Nie wyspałeś się czy co się z tobą dzieje?

0. Wiem, celowo nie ruszałem.
1. Np. dla liczba = 181063936.
2. W kilku postach poprawiałem na pierwiastkowanie przed pętlą, znawcy pisali, że jest to niepotrzebne - kompilator sam się połapie.
3. Wiem, celowo zostawiłem oryginalne pętle.
4. Nie rozumiem, obie wersje działają błędnie dla 1 i 2, pierwsza działa poza tym poprawnie, druga daje dodatkowo zły wynik dla 4.

1. Mylisz się: http://ideone.com/QFFIEn
2. Znawcy, którzy uważają że istnieje tylko jeden słuszny kompilator, na tylko jeden słuszny system operacyjny?
3. Druga daje zły wynik dla 4, 12, 15, 20 i wiele innych

1. A czego niby kod z ideone dowodzi? Masz 100% pewności, że jeśli liczba n jest kwadratem liczby naturalnej, oraz b = long(sqrt(n)), to porównanie n == b*b zwróci true?
2. Nie pamiętam, nie chce mi się szukać. Niewykluczone, że był wśród nich @_13th_Dragon.
3. Mylisz się http://ideone.com/8xCWTp

1. Oczywiście że mam 100% pewność: całkowitaA-całkowitaB*całkowitaB = całkowitaC nie ma możliwości aby całkowitaC nagłe się stała zmiennoprzecinkową.
2. Wykluczone, od zawsze jestem przeciwnikiem polegania na optymalizatorach i sprzątaczkach.
3. while (dzielnik < sqrt(liczba) - 1); - w tym miejscu wchodzisz w tą dziwną sytuację że jak sqrt obliczy niezbyt dokładnie to źle liczymy np jeżeli liczba=49 - wyliczasz 5 zamiast 3

To jeśli mam podpowiedzieć to proszę. Funkcja z algorytmem zbierającym dzielniki. A że podpowiedź, to już sobie przerobisz na zliczanie i poprawisz tę "szkolną" wersję :-)

#include <vector>
#include <cmath>

std::vector<long> dividers(long value) {
    // Kontener na dzielniki
    std::vector<long> answer;
    // Zmienna pomocnicza do określania dodatkowego dzielnika
    long other_divider;
    // Na tym kończymy iterację
    long stop_divide = std::sqrt(value) + 1;

    // Pętla szukająca dzielników
    for(long divider = 1; divider < stop_divide; ++divider) {
        if((value % divider) == 0) {
            answer.push_back(divider);

            // Czy nie ma przypadkiem drugiego dzielnika? :-)
            other_divider = value / divider;
            if(divider != other_divider) {
                answer.push_back(other_divider);
            }
        }
    }
    return answer;
}

Zastanawiam się czy nie należy do tego zadania podejść zupełnie inaczej:
Ponieważ 18=233 oznacza to że szukane liczby muszą być podzielnie dokładnie przez trzy liczby pierwsze oraz muszą być podzielnie przez kwadrat dwóch z nich (tych liczb pierwszych), np: 22335, 22355, 23355

EDIT: Albo: 22222*3
Albo: 2^17
Czyli iloczyn z (ilość+1) wszystkich występujących (lub nie) liczb pierwszych w pełnym rozkładzie liczby.

Więc czy nie sensowniej będzie:

1. Wczytać liczby do tablicy
2. Znaleźć maksymalną MaxValue
3. Wyliczyć MaxPrime=(int)pow(MaxValue,1.0/5);
4. Sporządzić sito Eratostenesa do MaxPrime
5. Sporządzić listę liczb mających 18 podzielników, będzie ich (MaxPrime*(MaxPrime-1)*(MaxPrime-2)/6)*3 czyli dla MaxValue=1000000000 będzie to tylko 119133 liczb
6. Po czym posprawdzać czy wczytane czy znajdują się na zbudowanej liście.

Lub:

1. Wczytać liczby do tablicy
2. Znaleźć maksymalną MaxValue
3. Wyliczyć MaxPrime=(int)pow(MaxValue,1.0/5);
4. Sporządzić sito Eratostenesa do MaxPrime
5. Dla każdej wczytanej liczby:
6. • Ustawiamy: one=0; two=0;
7. • Dzielimy przez kolejną liczbę pierwszą i zliczamy ile razy się podzieliło jeżeli doiliśmy to koniec sprawdzenia tej wczytanej liczby - nie będzie 18 -tu dzielników
8. • jeżeli wyszło dwa dzielniki to zwiększamy two i jeżeli two doszło do 3 to koniec sprawdzenia tej wczytanej liczby - nie będzie 18 -tu dzielników
9. • jeżeli wyszedł jeden dzielnik to zwiększamy one i jeżeli one doszło do 2 to koniec sprawdzenia tej wczytanej liczby - nie będzie 18 -tu dzielników
10. • kontynuujemy dla kolejnej liczby pierwszej
11. jeżeli two==2 oraz one==1 to mamy liczbę z 18 podzielnikami
12. bierzemy kolejną wczytaną liczbę
    </del>