64 lines
1.7 KiB
Text
64 lines
1.7 KiB
Text
include xpllib; \for Print
|
|
|
|
func Sieve(Limit, Primes); \Return Primes array and its size
|
|
int Limit, Primes;
|
|
char C;
|
|
int I, P, P2, N;
|
|
[C:= Reserve(Limit+1);
|
|
for I:= 0 to Limit do C(I):= false;
|
|
P:= 3; \no need to process even numbers
|
|
P2:= P*P;
|
|
while P2 <= Limit do
|
|
[I:= P2;
|
|
while I <= Limit do
|
|
[C(I):= true; I:= I + 2*P];
|
|
repeat P:= P+2 until C(P) = false;
|
|
P2:= P*P;
|
|
];
|
|
N:= 0;
|
|
for I:= 3 to Limit do
|
|
[if C(I) = false then [Primes(N):= I; N:= N+1];
|
|
I:= I+1;
|
|
];
|
|
return N;
|
|
];
|
|
|
|
func FindPeriod(N); \Return the period of the reciprocal of N
|
|
int N;
|
|
int I, R, RR, Period;
|
|
[R:= 1;
|
|
for I:= 1 to N+1 do
|
|
R:= rem((10*R) / N);
|
|
RR:= R;
|
|
Period:= 0;
|
|
repeat R:= rem((10*R) / N);
|
|
Period:= Period+1;
|
|
until R = RR;
|
|
return Period;
|
|
];
|
|
|
|
int I, Prime, Count, Index, PrimeCount, LongCount;
|
|
int Primes(6500), LongPrimes, Totals(8), Numbers;
|
|
[Numbers:= [500, 1000, 2000, 4000, 8000, 16000, 32000, 64000];
|
|
PrimeCount:= Sieve(64000, Primes);
|
|
LongPrimes:= Reserve(PrimeCount*IntSize);
|
|
LongCount:= 0;
|
|
for I:= 0 to PrimeCount-1 do \surely LongCount < PrimeCount
|
|
[Prime:= Primes(I);
|
|
if FindPeriod(Prime) = Prime-1 then
|
|
[LongPrimes(LongCount):= Prime; LongCount:= LongCount+1];
|
|
];
|
|
Count:= 0; Index:= 0;
|
|
for I:= 0 to LongCount-1 do
|
|
[if LongPrimes(I) > Numbers(Index) then
|
|
[Totals(Index):= Count; Index:= Index+1];
|
|
Count:= Count+1;
|
|
];
|
|
Totals(8-1):= Count;
|
|
Print("The long primes up to %d are:\n", Numbers(0));
|
|
for I:= 0 to Totals(0)-1 do
|
|
Print("%d ", LongPrimes(I));
|
|
Print("\n\nThe number of long primes up to:\n");
|
|
for I:= 0 to 8-1 do
|
|
Print(" %5d is %d\n", Numbers(I), Totals(I));
|
|
]
|