diff options
| author | Andrew Guschin <guschin.drew@gmail.com> | 2022-12-29 15:20:32 +0400 |
|---|---|---|
| committer | Andrew Guschin <guschin.drew@gmail.com> | 2022-12-29 15:20:32 +0400 |
| commit | 0be2be0a92f992bf8ee9eff701cb19658a1e7544 (patch) | |
| tree | 5d855004fd8cc067a594475c0a666eb01f0ceefa /lab9/lab9.py | |
| parent | 056f59346b727c9367998a423551eaba52854fce (diff) | |
Diffstat (limited to 'lab9/lab9.py')
| -rw-r--r-- | lab9/lab9.py | 84 |
1 files changed, 84 insertions, 0 deletions
diff --git a/lab9/lab9.py b/lab9/lab9.py new file mode 100644 index 0000000..5024088 --- /dev/null +++ b/lab9/lab9.py @@ -0,0 +1,84 @@ +import math
+import random
+
+
+def erathosphene(n):
+ is_prime = [True] * n
+ p = 2
+ while p * p < n:
+ cur = p * p;
+ while cur < n:
+ is_prime[cur] = False;
+ cur += p;
+ while not is_prime[p + 1]:
+ p += 1;
+ p += 1
+ primes = []
+ for i, p in enumerate(is_prime):
+ if p:
+ primes.append(i)
+ return primes[2:]
+
+
+def get_only_prime_divisors(n):
+ factors = []
+ if (n % 2 == 0):
+ factors.append(2)
+
+ while (n % 2 == 0):
+ n = n // 2
+
+ for i in range(3, int(math.sqrt(n)) + 1, 2):
+ if (n % i == 0):
+ factors.append(i)
+
+ while (n % i == 0):
+ n = n // i
+
+ if (n > 2):
+ factors.append(n)
+
+ return factors
+
+
+def lucas_test(n):
+ prev_n = n - 1
+ prime_divisors = get_only_prime_divisors(prev_n)
+ for a in range(2, n):
+ is_prime = True
+ if pow(a, prev_n, n) != 1:
+ continue
+ for q in prime_divisors:
+ if pow(a, prev_n // q, n) == 1:
+ is_prime = False
+ break
+ if is_prime:
+ return True
+ return False
+
+
+def get_random_number(n):
+ while True:
+ number = random.randrange(2 ** (n - 1) + 1, 2 ** n - 1)
+ if number % 2 == 0:
+ continue
+ for divisor in first_primes_list:
+ if number % divisor == 0 and divisor ** 2 <= number:
+ break
+ else:
+ return number
+
+
+def create_prime(n):
+ while True:
+ number = get_random_number(n)
+ if lucas_test(number):
+ return number
+
+
+first_primes_list = erathosphene(500)
+if __name__ == "__main__":
+ print("Введите количество бит генерируемого простого числа:")
+ n = int(input())
+ result = create_prime(n)
+ print(f"Сгенерированное простое число: {result}")
|