Verbeterde Zeef van Eratosthenes

Eén van de oudste methodes om priemgetallen te vinden is de Zeef van Eratosthenes. Bij deze methode worden de natuurlijke getallen in een matrix gezet. Daarna worden de getallen één voor één getest of die deelbaar zijn door alle priemgetallen die kleiner zijn dan √N, waarbij N is het grootste getal in de matrix is. De getallen die deelbaar zijn worden doorgestreept. De niet doorgestreepte getallen zijn de priemgetallen. Dit is monnikenwerk.

Bij de Zeef van Eratosthenes worden de getallen in een matrix gezet en getest of de getallen deelbaar zijn. Daarbij worden geen voorwaarden gesteld. Het aantal kolommen is te kiezen evenals de volgorde van de priemgetallen waarmee getest wordt. Bij het gebruik van een matrix met 10 kolommen blijkt, dat er kolommen zijn waarop alle getallen doorgestreept zijn en er zijn kolommen waarop enkele getallen doorgestreept zijn. Het getal voor getal testen is tijdrovend.

1	2	3	4	5	6	7	8	9	10		1	2	3	4	5	6	7	8	9	10		2	3	7
11	12	13	14	15	16	17	18	19	20		11	12	13	14	15	16	17	18	19	20		11	13	17	19
21	22	23	24	25	26	27	28	29	30		21	22	23	24	25	26	27	28	29	30			23		29
31	32	33	34	35	36	37	38	39	40		31	32	33	34	35	36	37	38	39	40		31		37
41	42	43	44	45	46	47	48	49	50		41	42	43	44	45	46	47	48	49	50		41	43	47
51	52	53	54	55	56	57	58	59	60		51	52	53	54	55	56	57	58	59	60			53		59
61	62	63	64	65	66	67	68	69	70		61	62	63	64	65	66	67	68	69	70		61		67
71	72	73	74	75	76	77	78	79	80		71	72	73	74	75	76	77	78	79	80		71	73		79
81	82	83	84	85	86	87	88	89	90		81	82	83	84	85	86	87	88	89	90			83		89
91	92	93	94	95	96	97	98	99	100		91	92	93	94	95	96	97	98	99	100				97

10 kolommen matrix met 100 getallen

10 kolommen matrix met doorgehaalde deelbare getallen.

de priemgetallen van 10 kolommen

Tabel: De getallen en het resultaat van het zeven met de Zeef van Eratosthenes.

Als er nu gewerkt wordt met een matrix van 30 kolommen dan worden alle getallen op een kolom in één keer getest of die deelbaar zijn door één van de drie kleinste priemgetallen 2, 3 of 5. Dit volgt uit de volgende lemna.
(30 = 2 x 3 x 5 = #5. #5 is de notatie van priemoriaal 5. Bij 30 kolommen is het verschil tussen twee op één volgende getallen op een kolom 30.)

Lemna: Als d|a en d|b dan d|(a +b). 
In woorden: als getal d een deler is van getal a en d is een deler van getal b, dan is d ook een deler van de som van a+b. d is het priemgetal waar mee getest wordt. a is het eerste getal op een kolom. b is n x 30. Als a deelbaar is door 2, 3 of 5 dan zijn alle getallen op de kolom waarop a ligt deelbaar door 2, 3 of 5, want b is ook deelbaar door 2, 3 en 5.

Het werken met een matrix van 30 kolommen laat zien, dat alle veelvouden van 2 op 15 van de 30 kolommen liggen. Alle veelvouden van 3 die geen veelvoud van 2 zijn, op 5 van de 30 kolommen liggen. Alle veelvouden van 5 die geen veelvoud van 2 en of 3 zijn, op 2 van de 30 kolommen liggen. Alle getallen van 22 van de 30 kolommen zijn deelbaar door 2, 3 en of 5 en dat is 73,3%.

1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30
31	32	33	34	35	36	37	38	39	40	41	42	43	44	45	46	47	48	49	50	51	52	53	54	55	56	57	58	59	60
61	62	63	64	65	66	67	68	69	70	71	72	73	74	75	76	77	78	79	80	81	81	83	84	85	86	87	88	89	90

Tabel: 3 rijen van de 30-kolommen matrix.

Bij 210 kolommen staan ook de veelvouden van 7 onder elkaar. Omdat 30 getallen op één regel van een A4-tje kunnen staan, wordt er voor 30-kolommen gekozen.

2

3

–

5

–

7

–

–

–

11

–

13

–

–

–

17

–

19

–

–

–

23

–

–

–

–

–

29

–

31

–

–

–

–

–

37

–

–

–

41

–

43

–

–

–

47

–

–

–

–

–

53

–

–

–

–

–

59

–

61

–

–

–

–

–

67

–

–

–

71

–

73

–

–

–

–

–

79

–

–

–

83

–

–

–

–

–

89

–

Tabel: 3 rijen van de gezeefde 30-kolommen matrix

Als de priemgetallen 2, 3, 5 en 7 in een aparte rij gezet worden en de veelvouden van 2, 3 en 5 weggelaten worden, dan blijven er slechts 8 van de 30 kolommen over. 2 is het enige even priemgetal en 5 is het enige priemgetal dat op met het cijfer 5 eindigt.

Het resultaat van dit zeven is:

1. De vier kleinste priemgetallen komen in een aparte rij te staan: 2, 3, 5, 7
2. De priemgetallen staan tussen samengestelde getallen in 8 kolommen.
3. Er is een periodiciteit van 30 getallen.

11   13   17   19      23   29        31   37
41   43   47   49      53   59        61   67
71   73   77   79      83   89        91   97

Tabel: 3 rijen van de 8- kolommen matrix.

De getallen die op één rij liggen komen uit een interval van 30 getallen.
1. Er liggen maximaal 8 priemgetallen op één rij.
4 priemgetallen op één decade en op de andere twee decades 2 priemgetallen per decade.
2. Er liggen maximaal 3 priemparen op één rij.
Eén priempaar op de kolommen 1 en 2, één op de kolommen 3 en 4 en één op de kolommen 6 en 7.