Проблема: Проверка первичности бесконечного целого числа, хранящихся в двойном связанном списке ⇐ C++

[Anonymous]

У меня была прекрасная возможность поручить написать программу, решая это, к сожалению, дата срока прошла, и мой код был пронизан логическими ошибками ... но я не хочу просто бросать полотенце. Пожалуйста, я умоляю, что вы взломанные программисты из переполнения стека (что от вас осталось), напишите свое решение для этого и откройте глаза, чтобы увидеть путь. (Требования ниже) < /p>
-n Значения: # цифры для бесконечной точности арифметики: с n = 10, 20, 40, 80, 160 < /p>
- Медленная и быстрая проверка первичности для неограниченных чистых целых чисел: чтобы проверить, является ли число n Prime.
-preferred: целые числа произвольной точности будут сохранены с помощью вдвойне связанных списков. -cecptable: динамический массив целых чисел.Program infinteger;

{$mode objfpc}{$H+}

uses

{$IFDEF UNIX}
cthreads,
{$ENDIF}
Classes,
SysUtils, Dos;

type
PNode = ^TNode;
TNode = record
digit: Integer;
next, prev: PNode;
end;

var
m: Integer; // Global variable to count operations

procedure AppendDigit(var head, tail: PNode; digit: Integer);
var
newNode: PNode;
begin
New(newNode);
newNode^.digit := digit;
newNode^.next := nil;
newNode^.prev := tail;

if tail nil then
tail^.next := newNode;

tail := newNode;
if head = nil then
head := newNode;

m := m + 1; // Count the operation of creating a new node
end;

// Function to generate a large integer of given length
function GenerateLargeInteger(length: Integer): PNode;
var
i: Integer;
head, tail: PNode;
begin

head := nil;
tail := nil;

for i := 1 to length do
begin
AppendDigit(head, tail, Random(9) + 1);
AppendDigit(head, tail, Random(10));
m := m + 1; // Count the operation of generating a random digit
end;

GenerateLargeInteger := head;
end;

function ModLinkedList(n: PNode; d: Integer): Integer;
var
remainder: Integer;
begin
if d = 0 then
begin
ModLinkedList := 0; // Handle division by zero
Exit;
end;

remainder := 0;
while n nil do
begin
remainder := (remainder * 10 + n^.digit) mod d;
n := n^.next;
m := m + 2; // Count multiplication and mod operation
end;
ModLinkedList := remainder;
end;

function IsPrimeSlow(n: PNode): Boolean;
var
i: Integer;
begin
if (n^.digit = 1) and (n^.next = nil) then
begin
IsPrimeSlow := False;
Exit;
end;

for i := 2 to 1000 do // Check divisibility up to a reasonable limit
begin
if ModLinkedList(n, i) = 0 then
begin
IsPrimeSlow := False;
Exit;
end;
m := m + 1; // Count division check
end;

IsPrimeSlow := True;
end;

function PowerModLinkedList(base, exponent, modulus: Integer): Integer;
var
res: Integer;
begin
if modulus = 0 then
begin
PowerModLinkedList := 0; // Handle division by zero
Exit;
end;

res := 1;
base := base mod modulus;
while exponent > 0 do
begin
if (exponent mod 2 = 1) then
res := (res * base) mod modulus;

exponent := exponent div 2;
base := (base * base) mod modulus;
m := m + 3; // Count operations
end;
PowerModLinkedList := res;
end;

function IsPrimeFast(n: PNode): Boolean;
const
Bases: array[1..5] of Integer = (2, 3, 5, 7, 11);
var
d, r, a, x, i, j: Integer;
temp: PNode;
begin
if (n^.digit = 1) and (n^.next = nil) then
begin
IsPrimeFast := False; // 1 is not a prime number
Exit;
end;

if ModLinkedList(n, 2) = 0 then
begin
IsPrimeFast := False; // Even numbers greater than 2 are not prime
Exit;
end;

// Compute d and r such that n - 1 = 2^r * d
d := 0;
r := 0;
temp := n;
while ModLinkedList(temp, 2) = 0 do
begin
d := d div 2;
r := r + 1;
m := m + 2;
end;

for i := 1 to 5 do
begin
a := Bases;
x := PowerModLinkedList(a, d, ModLinkedList(n, a));

if (x = 1) or (x = ModLinkedList(n, a) - 1) then
Continue;

for j := 1 to r - 1 do
begin
x := (x * x) mod ModLinkedList(n, a);
if x = 1 then
begin
IsPrimeFast := False;
Exit;
end;
if x = ModLinkedList(n, a) - 1 then
Break;
end;

if x ModLinkedList(n, a) - 1 then
begin
IsPrimeFast := False;
Exit;
end;
end;

IsPrimeFast := True;
end;

procedure PrintInfiniteInteger(head: PNode; var outputFile: TextFile);
begin
if head = nil then Exit;
PrintInfiniteInteger(head^.next, outputFile);
Write(outputFile, head^.digit);
end;

var
n: PNode;
seedFactor: QWord;
outputFile: TextFile;
sizes: array[1..5] of Integer = (10, 20, 40, 80, 160);
i, size: Integer;
begin
m := 0; // Initialize operation counter
seedFactor := QWord(@m) xor QWord(Now * 1000000);
RandSeed := seedFactor;

// Open the output file
AssignFile(outputFile, 'infinteger.txt');
Rewrite(outputFile);

// Iterate over required sizes
for i := 1 to 5 do
begin
size := sizes;

RandSeed := RandSeed + 555555555;
n := GenerateLargeInteger(size);

WriteLn(outputFile, '===== n = ', size, ' =====');

Write(outputFile, 'n = ');
PrintInfiniteInteger(n, outputFile);
WriteLn(outputFile);

// Check if n is prime using both methods
WriteLn(outputFile, 'Checking if n is prime:');
Write(outputFile, 'IsPrimeSlow: ');
if IsPrimeSlow(n) then
WriteLn(outputFile, 'Yes')
else
WriteLn(outputFile, 'No');

Write(outputFile, 'IsPrimeFast: ');
if IsPrimeFast(n) then
WriteLn(outputFile, 'Yes')
else
WriteLn(outputFile, 'No');

// Display the number of operations
WriteLn(outputFile, 'Number of operations (m): ', m);
WriteLn(outputFile);
end;

// Close the output file
CloseFile(outputFile);
end.


Подробнее здесь: https://stackoverflow.com/questions/794 ... inked-list