Sieve of Eratosthenes

The sieve of Eratosthenes, named after Eratosthenes of Cyrene, is a simple algorithm dating from Greek antiquity giving all the prime numbers (A000040) up to a specified integer in a rectangular array, by identifying the primes one by one and crossing off their multiples. Often it is presented as a 10 × 10 array showing the 25 primes up to 100.

It is especially convenient to have 30 numbers per row since 30 = 2 × 3 × 5 is a primorial number with a good size for a table, the previous primorial number 6 = 2 × 3 being rather too small and the next primorial number 210 = 2 × 3 × 5 × 7 being rather too large for a table. Excluding the prime factors of 30 (2, 3, 5), since there are eight congruences (mod 30) which are relatively prime to 30 (i.e.

φ (30) = 8

 ), the congruence classes {1, 7, 11, 13, 17, 19, 23, 29} (mod 30) or equivalently { ±1, ±3, ±7, ±11} (mod 30), any other prime may only appear among those. We need only apply the sieving algorithm for primes up to

⌊   2√  n ⌋

, thus for a square array like 30 × 30, we need only consider the primes from the first row for the sieving process.

Note that apart from the twin prime pairs {3, 5} and {5, 7}, any other twin prime pairs must be among the congruence pairs {0 ± 1}, {12 ± 1} and {18 ± 1} (mod 30). Also, apart from the cousin prime pair {3, 7}, any cousin prime pairs must be among the congruence pairs {9 ± 2}, {15 ± 2} and {21 ± 2} (mod 30) (see prime constellations).

Since the odd numbers are in arithmetic progression, the sieve algorithm may be applied to the odd numbers only, saving half the space.

Table of sieved integers

Table of sieved integers 1 to 900 = 30 2, where the sieving has to be done with only the primes up to 30 (first row)

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	82	83	84	85	86	87	88	89	90
91	92	93	94	95	96	97	98	99	100	101	102	103	104	105	106	107	108	109	110	111	112	113	114	115	116	117	118	119	120
121	122	123	124	125	126	127	128	129	130	131	132	133	134	135	136	137	138	139	140	141	142	143	144	145	146	147	148	149	150
151	152	153	154	155	156	157	158	159	160	161	162	163	164	165	166	167	168	169	170	171	172	173	174	175	176	177	178	179	180
181	182	183	184	185	186	187	188	189	190	191	192	193	194	195	196	197	198	199	200	201	202	203	204	205	206	207	208	209	210
211	212	213	214	215	216	217	218	219	220	221	222	223	224	225	226	227	228	229	230	231	232	233	234	235	236	237	238	239	240
241	242	243	244	245	246	247	248	249	250	251	252	253	254	255	256	257	258	259	260	261	262	263	264	265	266	267	268	269	270
271	272	273	274	275	276	277	278	279	280	281	282	283	284	285	286	287	288	289	290	291	292	293	294	295	296	297	298	299	300
301	302	303	304	305	306	307	308	309	310	311	312	313	314	315	316	317	318	319	320	321	322	323	324	325	326	327	328	329	330
331	332	333	334	335	336	337	338	339	340	341	342	343	344	345	346	347	348	349	350	351	352	353	354	355	356	357	358	359	360
361	362	363	364	365	366	367	368	369	370	371	372	373	374	375	376	377	378	379	380	381	382	383	384	385	386	387	388	389	390
391	392	393	394	395	396	397	398	399	400	401	402	403	404	405	406	407	408	409	410	411	412	413	414	415	416	417	418	419	420
421	422	423	424	425	426	427	428	429	430	431	432	433	434	435	436	437	438	439	440	441	442	443	444	445	446	447	448	449	450
451	452	453	454	455	456	457	458	459	460	461	462	463	464	465	466	467	468	469	470	471	472	473	474	475	476	477	478	479	480
481	482	483	484	485	486	487	488	489	490	491	492	493	494	495	496	497	498	499	500	501	502	503	504	505	506	507	508	509	510
511	512	513	514	515	516	517	518	519	520	521	522	523	524	525	526	527	528	529	530	531	532	533	534	535	536	537	538	539	540
541	542	543	544	545	546	547	548	549	550	551	552	553	554	555	556	557	558	559	560	561	562	563	564	565	566	567	568	569	570
571	572	573	574	575	576	577	578	579	580	581	582	583	584	585	586	587	588	589	590	591	592	593	594	595	596	597	598	599	600
601	602	603	604	605	606	607	608	609	610	611	612	613	614	615	616	617	618	619	620	621	622	623	624	625	626	627	628	629	630
631	632	633	634	635	636	637	638	639	640	641	642	643	644	645	646	647	648	649	650	651	652	653	654	655	656	657	658	659	660
661	662	663	664	665	666	667	668	669	670	671	672	673	674	675	676	677	678	679	680	681	682	683	684	685	686	687	688	689	690
691	692	693	694	695	696	697	698	699	700	701	702	703	704	705	706	707	708	709	710	711	712	713	714	715	716	717	718	719	720
721	722	723	724	725	726	727	728	729	730	731	732	733	734	735	736	737	738	739	740	741	742	743	744	745	746	747	748	749	750
751	752	753	754	755	756	757	758	759	760	761	762	763	764	765	766	767	768	769	770	771	772	773	774	775	776	777	778	779	780
781	782	783	784	785	786	787	788	789	790	791	792	793	794	795	796	797	798	799	800	801	802	803	804	805	806	807	808	809	810
811	812	813	814	815	816	817	818	819	820	821	822	823	824	825	826	827	828	829	830	831	832	833	834	835	836	837	838	839	840
841	842	843	844	845	846	847	848	849	850	851	852	853	854	855	856	857	858	859	860	861	862	863	864	865	866	867	868	869	870
871	872	873	874	875	876	877	878	879	880	881	882	883	884	885	886	887	888	889	890	891	892	893	894	895	896	897	898	899	900

The sieving algorithm

A. Write a range of integers in order into an array, usually starting with 1.

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	82	83	84	85	86	87	88	89	90

B. Choose a small prime, usually

p = 2

.
C. Circle or highlight

p

and cross out its square

p 2

and all its higher multiples that haven’t already been crossed off. (Note that 4 is crossed out, it just happens to fall on the horizontal bar of the numeral 4.)

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	82	83	84	85	86	87	88	89	90

D. Whichever number is to the right of

p

(or leftmost on the next row) that hasn’t been crossed off ought to be a prime. Circle or highlight it: it has now become

p

. If

p 2

is within the array, repeat Step C with the new

p

. Otherwise, you’re done.

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	82	83	84	85	86	87	88	89	90

...

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	82	83	84	85	86	87	88	89	90

Number of primes less than or equal to 2²ⁿ

A153450 Number of primes   ≤   2 2 n = PiPrime(A001146), n   ≥   0.

{1, 2, 6, 54, 6542, 203280221, ...}

The primes up to

2 2 n = (2 2 n  − 1 ) 2

are exactly determined from the primes up to

2 2 n  − 1, n   ≥   1,

with the sieve of Eratosthenes. This gives an inductive algorithm to find all primes up to any integer (modulo space and time constraints...) This means that all odd primes are ultimately determined by the only even prime, namely 2, the oddest prime... The primes less than or equal to

2 2 n, n   ≥   0,

where each subset is exactly determined by the preceding subset, are

{{2}, {2, 3}, {2, 3, 5, 7, 11, 13}, {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251}, ...}

Sequences

A001248 Squares of prime numbers.

{4, 9, 25, 49, 121, 169, 289, 361, 529, 841, 961, 1369, 1681, 1849, 2209, 2809, 3481, 3721, 4489, 5041, 5329, 6241, 6889, 7921, 9409, 10201, 10609, 11449, 11881, 12769, 16129, 17161, 18769, 19321, 22201, ...}

In doing the sieve of Eratosthenes, this sequence gives the first composite number that you’ll cross off after you identify the

n

th prime (that is, unless you like to cross off again the composite numbers that have already been crossed off for a smaller prime factor—e.g., for the third prime, 5, the first number to cross off is 25, because 10, 15 and 20 should have already been crossed off for 2, 3 and 2 respectively.

See also

• Index entries for sequences generated by sieves
• Lucky numbers (generated by a different sieving algorithm)
• Ulam spiral

External links

• Rosetta Code implementations