#include <stdio.h>

int main()		//Và cuối cùng đến hàm main của chướng trình 
{
    unsigned long long n,t,y;	//Khai báo n, t, y
    printf("nhap so le n ");
    scanf("%ld",&n);
    printf("nhap t ");
    scanf("%ld",&t);		//Sau đó dùng hàm scanf để nhập n và t từ bàn phím 
    long r = timr(n - 1);	/*Sự dụng hàm tìm r để tìm r với tham số chuyền vào là n = 1
				  và gán giá trị đó cho r*/ 
    int s = tims((n - 1), r);	/*Hàm tìm s cũng như vậy với 2 tham số chuyền vào là n - 1 và r
				  và cũng gán nó cho s*/

    y= nhanbinhphuongcolap(t, r, n);	/*Sau đó sự dụng hàm nhân bình phương có lặp với 3 tham số 
					  truyền vào là t, r và n và gán nó cho y*/
    if((y != 1) && (y != (n - 1))){	//Sự dụng khối lệnh if nếu y khác 1 và y khác (n - 1)
        int j = 1;			//thì gán j = 1
        while((j <= (s - 1)) && (y != (n - 1))){	/*Sử dụng khối lệnh while trong if
						với điều kiện lặp là j <= (s - 1)) và (y != (n - 1) */
        y = (y * y) % n;	//và gán y = (y * y) % n
            if(y == 1){		//Nếu y = 1 
                 printf("la hop so");	//return n là hợp số
                  return 0;
               }
            j++;	//không thì j++
        }
        if(y != (n - 1)){	//và nếu y khác (n - 1)
            printf("la hop so");//thì cũng return n là hợp số
            return 0;
        }
    }

    printf("la so nguyen so");	//Kết thúc vòng lặp if return n là số nguyên tố
    return 0;
}

int timr(long n){		//Tạo hàm tìm s với 1 tham số chuyền vào n
    long s = 1;		//khai báo s = 1
    for(int i = 0; s <= n; i++){	//Gọi vòng lặp for đến khi nào s <= 0
        long r = n / s;			//cho r = n / s
        long c = n % s;			//và c = n % s
        if((c == 0) && (r % 2) != 0 && (r > 0)){	//Nếu c = 0 và (r%2) khác 0 và r > 0
            return r;			//Thì return r
        }
        s = s * 2;		//không thì s = s * 2
    }
    return 0;
}

int tims(long n,long r){	//Tạo hàm tìm s với 2 tham số chuyền vào n và r
    int s = n / r;		//Khai báo s = n / r
    long k = 1;			//và k = 1
    for(int i = 0; i <= n; i++){	//Gọi vòng lặp for chạy từ i = 0 cho đến i <= n
        if(s == k){			//Nếu s = k
            return i;			//Thì return i
        }
        k = k * 2;			//còn không thì k = k * 2
    }
    return 0;
}

int nhanbinhphuongcolap(unsigned long long a, unsigned long long r, unsigned long long n) { 
//Tạo hàm nhân bình phương có lặp với 3 tham số truyền vào a, r, n
        int b = 1;		//Khai báo b = 1, i = 0
        int i = 0;
	int y;		
        int c[100];		//và một mảng c gồm 100 phần tử 
        unsigned long long m = r ;	//Khai báo m và gán bằng r
        while (r  > 0) {	//Gọi vòng lặp while với điều kiện lặp là r > 0
            c[i] = r % 2;	//đầu tiên cho c[i] = r % 2
            r = r / 2;		//Sau đó cho gán r = r / 2
            i++;		//Và i++
        }
        if (m == 0) {		//kết thúc vòng lặp nếu m = 0
            y = b;		//Thì y = b
        } else {	
            int A = a;		//không thì khai báo A lớn và gán bằng a nhỏ
            for (int j = 0; j < i; j++) {
                if (j == 0) {		//Nếu j = 0
                    if (c[j] == 1) {	//và nếu c[j] = 1
                        b = A;		/Thì b = A lớn
                    }
                } else {
                    A = A * A % n;	//Không thì A = A*A % n
                    if (c[j] == 1) {	//Nếu c[j] = 1 
                        b = A * b % n;	//Thì b = A * b % n
                    }
                }
            }
        }
        y = b;		//Kết thúc khối lệnh đó gán y = b
        return y;	//Và return y
    }