Skip to content

Commit 5735467

Browse files
patrickyevsukovpatrickyevsukov
committed
Merge pull request kennyledet#454 from estuardolh/master
sieve of Eratosthenes: Pascal implementation
2 parents c962f0a + 643bca3 commit 5735467

2 files changed

Lines changed: 286 additions & 0 deletions

File tree

‎Sieve_of_Eratosthenes/Pascal/estuardolh/sieve.pas‎

Lines changed: 138 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,138 @@
1+
unit sieve;
2+
3+
interface
4+
5+
uses crt;
6+
7+
const
8+
n = 50; { n cells }
9+
10+
type
11+
Cell = Record
12+
marked : Boolean; { True if a number is marked, false if not. }
13+
number : Integer; { Number in cell }
14+
end;
15+
16+
Row = Array[0..n] of Cell; { A row is an array of Cells }
17+
PRow = ^Row; { Pointer Type of Row }
18+
procedure row_fill( var a_row : Row );
19+
procedure row_print( var a_row : Row );
20+
procedure row_mark( a_row : PRow ; p : Integer );
21+
function row_lastnotmarked( a_row : Row ; p : Integer ) : Integer;
22+
procedure row_solve( var a_row : Row );
23+
24+
implementation
25+
26+
{ row is filled of numbers from 2 to n+1 }
27+
procedure row_fill( var a_row : Row );
28+
var
29+
i: Integer;
30+
begin
31+
for i := 0 to n-1 do
32+
begin
33+
a_row[i].number := i+2;
34+
end;
35+
end;
36+
37+
{ print a row as follow:
38+
[ n-3 ], [ n-2 ], ... [ n ]
39+
40+
where a number not marked is white
41+
and a marked is red.
42+
43+
when is printed i_ln cells in a row then
44+
a new line is wrote
45+
}
46+
procedure row_print( var a_row : Row );
47+
var
48+
i: Integer;
49+
i_ln: Integer = 4;
50+
begin
51+
for i:= 0 to n-1 do
52+
begin
53+
textColor(White);
54+
if a_row[i].number < 10 then
55+
write('[ ')
56+
else
57+
begin
58+
write('[ ');
59+
end;
60+
61+
if a_row[i].marked = True then
62+
textColor(LightRed)
63+
else
64+
begin
65+
textColor(White);
66+
end;
67+
68+
write(a_row[i].number);
69+
textColor(White);
70+
write(' ], ');
71+
72+
if (i + 1) mod i_ln = 0 then
73+
writeln;
74+
75+
end;
76+
writeln;
77+
end;
78+
79+
{ mark cells where number is a multiple of p }
80+
procedure row_mark( a_row : PRow ; p : Integer );
81+
var i : Integer;
82+
begin
83+
for i := 0 to n-1 do
84+
begin
85+
if a_row^[i].number mod p = 0 then
86+
begin
87+
if a_row^[i].number > p then
88+
begin
89+
a_row^[i].marked := True;
90+
end;
91+
end;
92+
end;
93+
end;
94+
95+
{ return the last number not marked greater than p }
96+
function row_lastnotmarked( a_row : Row ; p : Integer ) : Integer;
97+
var
98+
i : Integer;
99+
begin
100+
for i := 0 to n-1 do
101+
begin
102+
if a_row[i].number > p then
103+
begin
104+
if a_row[i].marked = False then
105+
begin
106+
row_lastnotmarked := a_row[i].number;
107+
break;
108+
end;
109+
end;
110+
end;
111+
end;
112+
113+
{ Solve Sieve of Eratosthenes.
114+
Cells in Row that are not marked has prime numbers.
115+
}
116+
procedure row_solve( var a_row : Row );
117+
var
118+
i, p: Integer;
119+
begin
120+
p := 2; { first prime number }
121+
122+
for i := 0 to n-1 do
123+
begin
124+
{ determine when to stop marking }
125+
if p * p > n then
126+
begin
127+
break;
128+
end;
129+
130+
if a_row[i].number = p then
131+
begin
132+
row_mark( @a_row, p );
133+
p := row_lastnotmarked( a_row, p);
134+
end;
135+
end;
136+
end;
137+
138+
end.

‎Sieve_of_Eratosthenes/Pascal/estuardolh/sieve_test.pas‎

Lines changed: 148 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,148 @@
1+
program sieve_test;
2+
3+
uses crt, sieve;
4+
5+
{ Compare Cells not marked
6+
with given prime numbers
7+
}
8+
procedure check( a_row: Row ; prime_numbers : Array of Integer );
9+
var
10+
i : Integer;
11+
j : Integer = 0;
12+
begin
13+
for i := 0 to n-1 do
14+
begin
15+
if j < Length(prime_numbers) then
16+
begin
17+
if a_row[i].marked = False then
18+
begin
19+
if a_row[i].number <> prime_numbers[j] then
20+
begin
21+
write(a_row[i].number);
22+
writeln(' is not prime.');
23+
exit;
24+
end;
25+
j := j + 1;
26+
end;
27+
end;
28+
end;
29+
30+
write('OK, All cells not marked have primes.');
31+
end;
32+
33+
var
34+
a_row : Row;
35+
begin
36+
clrScr;
37+
38+
row_fill( a_row );
39+
row_solve( a_row );
40+
row_print( a_row );
41+
42+
{ first 1000 primes
43+
https://primes.utm.edu/lists/small/1000.txt
44+
}
45+
check( a_row,
46+
[ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29
47+
, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71
48+
, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113
49+
, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173
50+
, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229
51+
, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281
52+
, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349
53+
, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409
54+
, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463
55+
, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541
56+
, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601
57+
, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659
58+
, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733
59+
, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809
60+
, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863
61+
, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941
62+
, 947, 953, 967, 971, 977, 983, 991, 997,1009,1013
63+
,1019,1021,1031,1033,1039,1049,1051,1061,1063,1069
64+
,1087,1091,1093,1097,1103,1109,1117,1123,1129,1151
65+
,1153,1163,1171,1181,1187,1193,1201,1213,1217,1223
66+
,1229,1231,1237,1249,1259,1277,1279,1283,1289,1291
67+
,1297,1301,1303,1307,1319,1321,1327,1361,1367,1373
68+
,1381,1399,1409,1423,1427,1429,1433,1439,1447,1451
69+
,1453,1459,1471,1481,1483,1487,1489,1493,1499,1511
70+
,1523,1531,1543,1549,1553,1559,1567,1571,1579,1583
71+
,1597,1601,1607,1609,1613,1619,1621,1627,1637,1657
72+
,1663,1667,1669,1693,1697,1699,1709,1721,1723,1733
73+
,1741,1747,1753,1759,1777,1783,1787,1789,1801,1811
74+
,1823,1831,1847,1861,1867,1871,1873,1877,1879,1889
75+
,1901,1907,1913,1931,1933,1949,1951,1973,1979,1987
76+
,1993,1997,1999,2003,2011,2017,2027,2029,2039,2053
77+
,2063,2069,2081,2083,2087,2089,2099,2111,2113,2129
78+
,2131,2137,2141,2143,2153,2161,2179,2203,2207,2213
79+
,2221,2237,2239,2243,2251,2267,2269,2273,2281,2287
80+
,2293,2297,2309,2311,2333,2339,2341,2347,2351,2357
81+
,2371,2377,2381,2383,2389,2393,2399,2411,2417,2423
82+
,2437,2441,2447,2459,2467,2473,2477,2503,2521,2531
83+
,2539,2543,2549,2551,2557,2579,2591,2593,2609,2617
84+
,2621,2633,2647,2657,2659,2663,2671,2677,2683,2687
85+
,2689,2693,2699,2707,2711,2713,2719,2729,2731,2741
86+
,2749,2753,2767,2777,2789,2791,2797,2801,2803,2819
87+
,2833,2837,2843,2851,2857,2861,2879,2887,2897,2903
88+
,2909,2917,2927,2939,2953,2957,2963,2969,2971,2999
89+
,3001,3011,3019,3023,3037,3041,3049,3061,3067,3079
90+
,3083,3089,3109,3119,3121,3137,3163,3167,3169,3181
91+
,3187,3191,3203,3209,3217,3221,3229,3251,3253,3257
92+
,3259,3271,3299,3301,3307,3313,3319,3323,3329,3331
93+
,3343,3347,3359,3361,3371,3373,3389,3391,3407,3413
94+
,3433,3449,3457,3461,3463,3467,3469,3491,3499,3511
95+
,3517,3527,3529,3533,3539,3541,3547,3557,3559,3571
96+
,3581,3583,3593,3607,3613,3617,3623,3631,3637,3643
97+
,3659,3671,3673,3677,3691,3697,3701,3709,3719,3727
98+
,3733,3739,3761,3767,3769,3779,3793,3797,3803,3821
99+
,3823,3833,3847,3851,3853,3863,3877,3881,3889,3907
100+
,3911,3917,3919,3923,3929,3931,3943,3947,3967,3989
101+
,4001,4003,4007,4013,4019,4021,4027,4049,4051,4057
102+
,4073,4079,4091,4093,4099,4111,4127,4129,4133,4139
103+
,4153,4157,4159,4177,4201,4211,4217,4219,4229,4231
104+
,4241,4243,4253,4259,4261,4271,4273,4283,4289,4297
105+
,4327,4337,4339,4349,4357,4363,4373,4391,4397,4409
106+
,4421,4423,4441,4447,4451,4457,4463,4481,4483,4493
107+
,4507,4513,4517,4519,4523,4547,4549,4561,4567,4583
108+
,4591,4597,4603,4621,4637,4639,4643,4649,4651,4657
109+
,4663,4673,4679,4691,4703,4721,4723,4729,4733,4751
110+
,4759,4783,4787,4789,4793,4799,4801,4813,4817,4831
111+
,4861,4871,4877,4889,4903,4909,4919,4931,4933,4937
112+
,4943,4951,4957,4967,4969,4973,4987,4993,4999,5003
113+
,5009,5011,5021,5023,5039,5051,5059,5077,5081,5087
114+
,5099,5101,5107,5113,5119,5147,5153,5167,5171,5179
115+
,5189,5197,5209,5227,5231,5233,5237,5261,5273,5279
116+
,5281,5297,5303,5309,5323,5333,5347,5351,5381,5387
117+
,5393,5399,5407,5413,5417,5419,5431,5437,5441,5443
118+
,5449,5471,5477,5479,5483,5501,5503,5507,5519,5521
119+
,5527,5531,5557,5563,5569,5573,5581,5591,5623,5639
120+
,5641,5647,5651,5653,5657,5659,5669,5683,5689,5693
121+
,5701,5711,5717,5737,5741,5743,5749,5779,5783,5791
122+
,5801,5807,5813,5821,5827,5839,5843,5849,5851,5857
123+
,5861,5867,5869,5879,5881,5897,5903,5923,5927,5939
124+
,5953,5981,5987,6007,6011,6029,6037,6043,6047,6053
125+
,6067,6073,6079,6089,6091,6101,6113,6121,6131,6133
126+
,6143,6151,6163,6173,6197,6199,6203,6211,6217,6221
127+
,6229,6247,6257,6263,6269,6271,6277,6287,6299,6301
128+
,6311,6317,6323,6329,6337,6343,6353,6359,6361,6367
129+
,6373,6379,6389,6397,6421,6427,6449,6451,6469,6473
130+
,6481,6491,6521,6529,6547,6551,6553,6563,6569,6571
131+
,6577,6581,6599,6607,6619,6637,6653,6659,6661,6673
132+
,6679,6689,6691,6701,6703,6709,6719,6733,6737,6761
133+
,6763,6779,6781,6791,6793,6803,6823,6827,6829,6833
134+
,6841,6857,6863,6869,6871,6883,6899,6907,6911,6917
135+
,6947,6949,6959,6961,6967,6971,6977,6983,6991,6997
136+
,7001,7013,7019,7027,7039,7043,7057,7069,7079,7103
137+
,7109,7121,7127,7129,7151,7159,7177,7187,7193,7207
138+
,7211,7213,7219,7229,7237,7243,7247,7253,7283,7297
139+
,7307,7309,7321,7331,7333,7349,7351,7369,7393,7411
140+
,7417,7433,7451,7457,7459,7477,7481,7487,7489,7499
141+
,7507,7517,7523,7529,7537,7541,7547,7549,7559,7561
142+
,7573,7577,7583,7589,7591,7603,7607,7621,7639,7643
143+
,7649,7669,7673,7681,7687,7691,7699,7703,7717,7723
144+
,7727,7741,7753,7757,7759,7789,7793,7817,7823,7829
145+
,7841,7853,7867,7873,7877,7879,7883,7901,7907,7919 ] );
146+
147+
readln;
148+
end.

0 commit comments

Comments
 (0)