Tổng các số nguyên tố cùng nhau

[socola]

mọi người giúp e với ạ.
e thử làm ra khi nhập 10 lại ra 17

[noname00 (HK boy)]

Code bạn thử làm đâu?

[socola]

bool ktsnt(int n)
{
    int i;
    if (n<2) return 0;
    for (i=2; i<=sqrt(n); i++)
        if (n%i==0)
            return 0;
    return 1;
}

int sumRelativePrime(int n)
{
    int i,s=0;
    for (i=0; i<n; i++)
        if (ktsnt(i)==1)
            s=s+i;
    return s;
}

xem giúp e với ạ

[tntxtnt]

nguyên tố cùng nhau với n là các số a sao cho ucln(n, a) = 1 ấy chứ ko phải a là số nguyên tố :V

[rogp10]

n= 2 thì chỉ có (1, n) = 1 nên kết quả bằng 1.

Xét n > 2:

• Nếu n chia hết cho một số nguyên tố lẻ: Do \phi(n) = n \times\prod\limits_{p | n}^{nguyên\ tố}\frac{p-1}{p} = \text{số nguyên} \times\prod\limits_{p | n}^{nguyên\ tố}(p-1) mà khi p lẻ thì p-1 chẵn, làm cho tích cũng chẵn. Vậy \phi(n) là số chẵn.

• Ngược lại, n là lũy thừa của 2 nên \phi(n) = n\cdot\frac{1}{2}, mà n chia hết cho 4 nên \phi(n) chẵn.

Do gcd(n, d) = 1 \Rightarrow gcd(n, n-d) = 1 nên có thể bắt cặp (n-d, d). Có cả thảy \frac{\phi(n)}{2} cặp như vậy nên tổng là n \times \frac{\phi(n)}{2}.