2-topshiriq 1091 soni ferma ususli #include int main { int a = 2; int n = 1091; // Fermaning kichik teoremasini hisoblash int result = 1; for (int i = 0; i < n 1; ++i) { result = (result a) n; } // Natijani chiqarish std:: cout

2-topshiriq

1. 
   1091 soni ferma ususli
   

#include

int main() {
int a = 2;
int n = 1091;

// Fermaning kichik teoremasini hisoblash

int result = 1;
for (int i = 0; i < n - 1; ++i) {
result = (result * a) % n;
}

// Natijani chiqarish

std::cout << result << std::endl;

return 0;

}


a=3;
#include

int main() {

int a = 3;
int n = 1091;

// Fermaning kichik teoremasini hisoblash

int result = 1;
for (int i = 0; i < n - 1; ++i) {
result = (result * a) % n;
}

// Natijani chiqarish

std::cout << result << std::endl;

return 0;

}

a=17;
#include

int main() {

int a = 17;
int n = 1091;

// Fermaning kichik teoremasini hisoblash

int result = 1;
for (int i = 0; i < n - 1; ++i) {
result = (result * a) % n;
}

// Natijani chiqarish

std::cout << result << std::endl;

return 0;

}

2.
#include
#include
#include

// (a^b) % mod

long long power(long long a, long long b, long long mod) {
long long result = 1;
a = a % mod;
while (b > 0) {
if (b % 2 == 1)
result = (result * a) % mod;
b = b / 2;
a = (a * a) % mod;
}
return result;
}

// Rabin-Miller tublikka tekshirish

bool tublikkatekshir(long long n, int k) {
if (n <= 1 || n == 4)
return false;
if (n <= 3)
return true;

// n-1 = 2^r * d

long long d = n - 1;
while (d % 2 == 0)
d /= 2;

for (int i = 0; i < k; i++) {

long long a = 2 + rand() % (n - 3);
long long x = power(a, d, n);

if (x == 1 || x == n - 1)

continue;

for (long long r = 1; r < n - 1; r *= 2) {

x = (x * x) % n;
if (x == 1)
return false;
if (x == n - 1)
break;
}

if (x != n - 1)

return false;
}

return true;

}

int main() {

long long A = 1091;

int k = 5;

if (tublikkatekshir(A, k))
std::cout << A << " Tub son bolishi mumkin ." << std::endl;
else
std::cout << A << " Tub son emas ." << std::endl;

return 0;

}