sieve of Eratosthenes qarbâl-e Eratosthenes (#) Fr.: crible d'Eratosthène A classical method of finding all → prime numbers up to any given number n. The method consists of listing all positive integers from 2 up to the given number and then deleting some of them sequentially in steps. For example, if we wish to find the primes less than or equal to 50, we proceed as follows. All integers from 2 to 50 are first written. The integers that are divisible by 2, other than 2, are crossed out from the list. Since 3 is the first integer greater than 2 that is not removed, all the integers divisible by 3, other than 3, are crossed out. We do the same with 5 and then 7. Since all composite integers ≤ 50 are divisible by 2, 3, 5, or 7 (i.e. ≤ √50), all the remaining integers not deleted are prime numbers: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, and 47. M.E. sive, O.E. sife "sieve;" cf. M.Du. seve, Du. zeef, O.H.G. sib, Ger. Sieb, of unknown origin. Related to sift. Qarbâl (variants qarbil, qarbir, qelber, qalbur, gerbâl), probably related to the PIE base *krei- "to sieve, separate;" cf. Gk. krinein "to separate, decide, judge," krisis "decision;" L. cribrum "sieve" (Fr. crible), cernere "to sift, separate;" O.E. hriddel "sieve;" O.Ir. criathar; O.Welsh cruitr "sieve." Pers. qarbâl loaned in Ar. as gharbala "to sift," itself loaned in It. garbellare; M.Fr. garbeler "to sift;" E. garble "to sift impurities from." |