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

0

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

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

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

0

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

0

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);
0

@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
  1. Wiem, celowo nie ruszałem.
  2. Np. dla liczba = 181063936.
  3. W kilku postach poprawiałem na pierwiastkowanie przed pętlą, znawcy pisali, że jest to niepotrzebne - kompilator sam się połapie.
  4. Wiem, celowo zostawiłem oryginalne pętle.
  5. 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.
0
  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
0
  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
0
  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
0

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;
}

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