Project Euler

[Ilias95]

Θα στο πω με παράδειγμα για να το καταλάβεις.

Το i είναι πάντα ο πρώτος αριθμός (πρώτος στην σειρά εννοώ) που έχει τέλεια διαίρεση με τον number.
Ας πούμε ότι ο number ισούται με 6798. Τότε ο i θα είναι 2.
Από την διαίρεση 6798 / 2 παίρνουμε το αποτέλεσμα 3399.

Προφανώς όλοι οι αριθμοί από το 3399 μέχρι το 6798 ΔΕΝ είναι διαιρέτες του 6798 οπότε δεν έχει νόημα να εξετάσουμε αν ο 6798 διαιρείται απ' αυτούς.
Οπότε συνεχίζουμε με αυτόν τον τρόπο να βρίσκουμε τους διαιρέτες μέχρι να βρούμε κάποιον που να είναι πρώτος αριθμός.
Ο πρώτος στην σειρά που θα βρούμε ότι είναι πρώτος αριθμός θα είναι και ο μέγιστος πρώτος διαιρέτης.
Προφανώς όλοι οι διαιρέτες που θα βρίσκουμε εκτός από διαιρέτες της τιμής που έχει ο number εκείνη την στιγμή θα είναι και διαιρέτες της πρώτης - πρώτης τιμής του number, δηλαδή του 6798. Γενικώς ισχύει ότι κάθε διαιρέτης ενός αριθμού x είναι και διαιρέτης των πολλαπλάσιων του x.

Επίσης πρόσεξε κάτι άλλο.
Το loop "for (; i < number; i++)" δεν δίνει εκ νέου τιμή στο i, αλλά κρατάει την τιμή του i στην οποία έχει φτάσει σε προηγούμενες επαναλήψεις.

Δηλαδή ένα άλλο παράδειγμα:
number = 62437, οπότε ο i στην διαίρεση θα είναι ο αριθμός 29.
Ο number θα γίνει δηλαδή: number = 62437 / 29 = 2153
Θα πρέπει να συνεχίσουμε να ψάχνουμε για διαιρέτες του 2153. Όμως ξέρουμε ότι οι διαιρέτες αυτοί θα είναι αναγκαστικά μεγαλύτεροι από 29 (το τελευταίο i).
Όλοι οι προηγούμενοι αριθμοί (2 - 29), αφού δεν διαιρούσαν το 62437 δεν θα διαιρούν ούτε το 2153.

Ελπίζω να κατάλαβες.

[stamatiou]

Ναι, αλλά στον κώδικα σε C, το 600851475143 δεν διαιρείται ακριβώς με το 2. Επίσης,όλα αυτά που λες, μου ακούγονται πρακτικά. Γίνεται να αποδείξεις κάπως πως δουλεύουν για όλους τους αριθμούς; (No offense πάντα, να καταλάβω τον τρόπο σκέψης σου προσπαθώ )

[pmav99]

Πχ ψάχνεις τους πρώτους παράγοντες του 125
Το 2 δεν είναι, το 3 δεν είναι, το 4 δεν είναι. Δοκιμάζεις το 5

125 % 5 == 0

Άρα το 5 είναι ένας παράγοντας. Άρα έχεις

125 = 5 * κ

Ο νέος αριθμός που έχεις να ψάξεις είναι το κ = 125 / 5 = 25. Δεν έχει νόημα να ψάξεις τους μεγαλύτερους αριθμούς.

[stamatiou]

Ναι αλλά γιατί αυτό δουλεύει για όλους τους αριθμούς;

[pmav99]

α) Ανοίγεις ένα βιβλίο θεωρίας αριθμών.
β) Δοκιμάζεις με το χέρι μέχρι να πειστείς

[Ilias95]

Ναι, αλλά στον κώδικα σε C, το 600851475143 δεν διαιρείται ακριβώς με το 2

Φυσικά.
Σου είπα ότι το i στην διαίρεση είναι ο μικρότερος διαιρέτης. Για το 600851475143 ο μικρότερος διαιρέτης είναι το 71.

Επίσης,όλα αυτά που λες, μου ακούγονται πρακτικά. Γίνεται να αποδείξεις κάπως πως δουλεύουν για όλους τους αριθμούς;

Σε τι ακριβώς θέλεις απόδειξη;

[stamatiou]

Δεν καταλαβαίνω γιατί αυτός ο αλγόριθμος θα δουλεύει με όλους τους αριθμούς :/

[Ilias95]

Δεν καταλαβαίνω γιατί αυτός ο αλγόριθμος θα δουλεύει με όλους τους αριθμούς :/

Αυτό το post μου το κατάλαβες; viewtopic.php?f=6&t=19509&start=60#p252017

Αν κολλάς στο:

Προφανώς όλοι οι αριθμοί από το 3399 μέχρι το 6798 ΔΕΝ είναι διαιρέτες του 6798 οπότε δεν έχει νόημα να εξετάσουμε αν ο 6798 διαιρείται απ' αυτούς.

Αν ψάξεις σε κάποιο βιβλίο θεωρίας αριθμών όπως πρότεινε ο Παναγιώτης ή στο internet, θα βρεις την απόδειξη.

[Ilias95]

Για να το καταλάβεις καλύτερα στο γυμνάσιο (;) αν θυμάμαι καλά είχαμε μάθει να αναλύουμε έναν αριθμό σε γινόμενο πρώτων παραγόντων.
Πχ. 288 = 2 * 2 * 2 * 2 * 2 * 3 * 3 = 2^5 * 3^2

Απ' το παραπάνω είναι φανερό ότι ο μέγιστος πρώτος παράγοντας του 288 είναι το 3.

[pmav99]

Κάθε αριθμος είναι ένα γινόμενο πρώτων παραγόντων

Το 1 = 1 * 1
Το 2 = 1 * 2
Το 3 = 1 * 3
Το 4 = 1 * 2 * 2
Το 5 = 1 * 5
Το 6 = 1 * 2 * 3
Το 7 = 1 * 7
Το 8 = 1 * 2 * 2 * 2
Το 9 = 1 * 3 * 3
Το 10 = 1 * 2 * 5
Το 11 = 1 * 11
Το 55 = 1 * 5 * 11
Το 99 = 1 * 3 * 3 * 11

Έστω ο αριθμός Ν είναι το γινόμενο n πρώτων αριθμών.
Ν = a,1 * a,2 * ... * a,n

Εσύ αρχικά ξέρεις τον Ν. Βρίσκεις έναν από τους παράγοντες. Έστω τον a,j. Άρα την παραπάνω ισότητα μπορείς να την γράψεις ως
M = N / a,j = a,1 * a,2 * .... * a,n-1

Αυτό είναι. Εχεις ένα νέο αριθμό Μ, όπου Μ < Ν και ο οποιός είναι το γινόμενο n-1 παραγόντων. Επαναλαμβάνεις την ίδια διαδικασία με προηγουμένως με το Μ αυτή τη φορά, αλλά επειδή Μ < Ν τελειώνεις πολύ πιο γρήγορα.

Αν θυμάμαι καλά υπάρχει και άλλη μια ιδιότητα που μπορείς να χρησιμοποιήσεις για να πας πιο γρήγορα. Στο loop δε χρειάζεται να ψάχνεις μέχρι το N αλλά μέχρι το sqrt(N).