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



Yüklə 255,21 Kb.
tarix21.12.2023
ölçüsü255,21 Kb.
#188369
OOOOOOOOOOOO


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;


}

Yüklə 255,21 Kb.

Dostları ilə paylaş:




Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©azkurs.org 2024
rəhbərliyinə müraciət

gir | qeydiyyatdan keç
    Ana səhifə


yükləyin