1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98
|
#include <stdio.h>
bool is_prime (size_t n);
size_t power (size_t a, size_t n, size_t mod);
bool witness (size_t n, size_t s, size_t d, size_t a);
int main (void)
{
size_t n, upper_prime, lower_prime, range;
printf ("Input= ");
scanf_s ("%zu", &n);
upper_prime = n;
while (!is_prime (upper_prime)) ++upper_prime;
lower_prime = n;
while (!is_prime (lower_prime)) --lower_prime;
range = upper_prime - lower_prime;
printf("1-) Upper Prime: %zu\n", upper_prime);
printf ("2-) Lower Prime: %zu\n", lower_prime);
printf ("3-) %zu-%zu=%zu",upper_prime,lower_prime,range);
}
size_t power (size_t a, size_t n, size_t mod)
{
size_t power = a;
size_t result = 1;
while (n)
{
if (n & 1)
result = (result * power) % mod;
power = (power * power) % mod;
n >>= 1;
}
return result;
}
bool witness (size_t n, size_t s,size_t d, size_t a)
{
size_t x = power (a, d, n);
size_t y = 0;
while (s)
{
y = (x * x) % n;
if (y == 1 && x != 1 && x != n - 1)
return false;
x = y;
--s;
}
if (y != 1)
return false;
return true;
}
bool is_prime (size_t n)
{
if (((!(n & 1)) && n != 2) || (n < 2) || (n % 3 == 0 && n != 3))
return false;
if (n <= 3)
return true;
size_t d = n / 2;
size_t s = 1;
while (!(d & 1))
{
d /= 2;
++s;
}
if (n < 1373653)
return witness (n, s, d, 2) && witness (n, s, d, 3);
if (n < 9080191)
return witness (n, s, d, 31) && witness (n, s, d, 73);
if (n < 4759123141)
return witness (n, s, d, 2) && witness (n, s, d, 7)
&& witness (n, s, d, 61);
if (n < 1122004669633)
return witness (n, s, d, 2) && witness (n, s, d, 13)
&& witness (n, s, d, 23) && witness (n, s, d, 1662803);
if (n < 2152302898747)
return witness (n, s, d, 2) && witness (n, s, d, 3)
&& witness (n, s, d, 5) && witness (n, s, d, 7)
&& witness (n, s, d, 11);
if (n < 3474749660383)
return witness (n, s, d, 2) && witness (n, s, d, 3)
&& witness (n, s, d, 5) && witness (n, s, d, 7)
&& witness (n, s, d, 11) && witness (n, s, d, 13);
return witness (n, s, d, 2) && witness (n, s, d, 3)
&& witness (n, s, d, 5) && witness (n, s, d, 7)
&& witness (n, s, d, 11) && witness (n, s, d, 13)
&& witness (n, s, d, 17);
}
|