12-11-2009, 19:28
|
|
|
חבר מתאריך: 25.09.09
הודעות: 63
|
|
תשתמש באלגוריתם "אוקלידס". זהו אלגוריתם למציאת המחלק המשותף הגדול ביותר של שני מספרים והוא עובד על העקרון הבא: די למצוא את המחלק המשותף המקסימלי של הקטן מבין 2 המספרים ושל שארית חלוקת הגדול בקטן. כאשר מגיעים לשארית 0, המספר שלפני - זהו המחלק המשותף הגדול ביותר של שני המספרים.
קוד PHP:
public static Euclid(int j, int k) { if (j % k == 0) return k; else return Euclid(k, j % k); {
לאחר שאתה מקבל את המחלק המשותף הגדול ביותר, החזר אמת אם הוא שונה מ-1, אחרת החזר שקר.
|