Phi function

الدرس 12 من 20 في دورة ألغاز رياضية على Coddy.

تُستخدم دالة مؤشر أويلر، φ(n) [تُسمى أحياناً دالة فاي]، لتحديد عدد الأعداد الأصغر من n والتي تُعد أولية بالنسبة لـ n. على سبيل المثال، بما أن 1، 2، 4، 5، 7، و 8، كلها أصغر من تسعة وأولية بالنسبة لتسعة (مما يعني أن القاسم المشترك الأكبر بين كل هذه الأعداد و 9 هو العدد 1)،

فإن نتيجة دالة فاي φ(9)=6. وبما أننا تعلمنا كيفية حساب GCD، يمكننا حساب دالة فاي (بمساعدة دالة GCD).

التحدي

صعب

اكتب دالة phi تستقبل رقماً n وتعيد قيمة φ(n).

جرّب بنفسك

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include "solution.h"

int main() {
    int n;
    if (scanf("%d", &n) != 1) n = 0;
    int r = phi(n);
    printf("%d\n", r);
    return 0;
}