program TenDigitPrimes;
{
This program finds:
1. The first 10-digit prime number.
2. The last 10-digit prime number.
Approach:
- Use 64-bit integers to safely hold 10-digit values.
- Implement a primality test using trial division up to sqrt(n).
This is efficient for checking individual numbers in this range.
- Search upward from the smallest 10-digit number for the first prime.
- Search downward from the largest 10-digit number for the last prime.
- Skip even numbers to reduce unnecessary work.
}
uses
Math; { for sqrt }
type
UInt64 = QWord;
{ Check whether a number is prime }
function IsPrime(n: UInt64): Boolean;
var
d, limit: UInt64;
begin
if n < 2 then
begin
IsPrime := False;
Exit;
end;
if (n mod 2 = 0) then
begin
IsPrime := (n = 2);
Exit;
end;
limit := Trunc(Sqrt(n));
d := 3;
while d <= limit do
begin
if (n mod d = 0) then
begin
IsPrime := False;
Exit;
end;
d := d + 2;
end;
IsPrime := True;
end;
{ Find the first 10-digit prime }
function First10DigitPrime: UInt64;
var
n: UInt64;
begin
n := 1000000000; { smallest 10-digit number }
if (n mod 2 = 0) then
Inc(n); { move to next odd number }
while not IsPrime(n) do
n := n + 2; { check only odd numbers }
First10DigitPrime := n;
end;
{ Find the last 10-digit prime }
function Last10DigitPrime: UInt64;
var
n: UInt64;
begin
n := 9999999999; { largest 10-digit number }
if (n mod 2 = 0) then
Dec(n); { move to previous odd number }
while not IsPrime(n) do
n := n - 2; { check only odd numbers }
Last10DigitPrime := n;
end;
var
first, last: UInt64;
begin
first := First10DigitPrime;
last := Last10DigitPrime;
WriteLn('First 10-digit prime: ', first);
WriteLn('Last 10-digit prime: ', last);
end.
{
run:
First 10-digit prime: 1000000007
Last 10-digit prime: 9999999967
}
