Δημοσιεύτηκε: 03 Ιούλ 2012, 18:40
Κάθε αριθμος είναι ένα γινόμενο πρώτων παραγόντων
Το 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).
Το 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).