15,745,504 members
Home / Discussions / C#

# C#

 Re: Sieve of Eratosthenes fjdiewornncalwe12-Sep-12 4:31 fjdiewornncalwe 12-Sep-12 4:31
 Re: Sieve of Eratosthenes Manfred Rudolf Bihy12-Sep-12 4:36 Manfred Rudolf Bihy 12-Sep-12 4:36
 Re: Sieve of Eratosthenes WebMaster12-Sep-12 4:39 WebMaster 12-Sep-12 4:39
 Re: Sieve of Eratosthenes Manfred Rudolf Bihy12-Sep-12 4:45 Manfred Rudolf Bihy 12-Sep-12 4:45
 Re: Sieve of Eratosthenes WebMaster12-Sep-12 4:56 WebMaster 12-Sep-12 4:56
 Re: Sieve of Eratosthenes Manfred Rudolf Bihy12-Sep-12 5:04 Manfred Rudolf Bihy 12-Sep-12 5:04
 Re: Sieve of Eratosthenes Richard MacCutchan12-Sep-12 5:40 Richard MacCutchan 12-Sep-12 5:40
 Re: Sieve of Eratosthenes J4amieC12-Sep-12 4:53 J4amieC 12-Sep-12 4:53
 According to wiki[^] "The sieve of Eratosthenes is one of the most efficient ways to find all of the smaller primes (below 10 million or so)." (Citation: The Prime Glossary: "The Sieve of Eratosthenes", http://primes.utm.edu/glossary/page.php?sort=SieveOfEratosthenes, references 16. November 2008.) That should answer your question; The algo is good for the range of numbes you've chosen. However (and thats a BIG however), your implementation is wrong. ```for i = 2, 3, 4, ..., √n : if A[i] is true: for j = i2, i2+i, i2+2i, ..., n: A[j] := false``` You've forgotton to only go to the square root of n (Think about why its only necessary to go to sqrt of n!), which takes a HUGE chunk off of the processing. Also, there should be no second `if`, in that part of the code, you've already multiplied 2 numbers together, so you know the result cannot be prime. All in all, youve implemented brute force, which is miles slower than the Sieve of Eratosthenesfor finding primes.
 Re: Sieve of Eratosthenes Pete O'Hanlon12-Sep-12 4:54 Pete O'Hanlon 12-Sep-12 4:54
 Re: Sieve of Eratosthenes WebMaster12-Sep-12 4:59 WebMaster 12-Sep-12 4:59
 Re: Sieve of Eratosthenes J4amieC12-Sep-12 5:02 J4amieC 12-Sep-12 5:02
 Re: Sieve of Eratosthenes Manfred Rudolf Bihy12-Sep-12 5:06 Manfred Rudolf Bihy 12-Sep-12 5:06
 Re: Sieve of Eratosthenes J4amieC12-Sep-12 5:07 J4amieC 12-Sep-12 5:07
 Re: Sieve of Eratosthenes Pete O'Hanlon12-Sep-12 5:04 Pete O'Hanlon 12-Sep-12 5:04
 Re: Sieve of Eratosthenes WebMaster12-Sep-12 5:16 WebMaster 12-Sep-12 5:16
 Re: Sieve of Eratosthenes Pete O'Hanlon12-Sep-12 5:22 Pete O'Hanlon 12-Sep-12 5:22
 Re: Sieve of Eratosthenes J4amieC12-Sep-12 5:23 J4amieC 12-Sep-12 5:23
 Re: Sieve of Eratosthenes WebMaster12-Sep-12 5:48 WebMaster 12-Sep-12 5:48
 Re: Sieve of Eratosthenes J4amieC12-Sep-12 5:59 J4amieC 12-Sep-12 5:59
 Re: Sieve of Eratosthenes WebMaster12-Sep-12 6:11 WebMaster 12-Sep-12 6:11
 Re: Sieve of Eratosthenes Rage12-Sep-12 6:23 Rage 12-Sep-12 6:23
 Re: Sieve of Eratosthenes Pete O'Hanlon12-Sep-12 6:25 Pete O'Hanlon 12-Sep-12 6:25
 Proper implementation of Sieve of Eratosthenes Clifford Nelson12-Sep-12 10:45 Clifford Nelson 12-Sep-12 10:45
 Re: Proper implementation of Sieve of Eratosthenes WebMaster12-Sep-12 11:00 WebMaster 12-Sep-12 11:00
 Re: Proper implementation of Sieve of Eratosthenes Clifford Nelson12-Sep-12 11:20 Clifford Nelson 12-Sep-12 11:20
 Last Visit: 31-Dec-99 18:00     Last Update: 28-Sep-23 14:18 Refresh ᐊ Prev1...1853185418551856185718581859186018611862 Next ᐅ