Click here to Skip to main content
15,443,549 members
Home / Discussions / C#
   

C#

 
AnswerRe: Sieve of Eratosthenes Pin
fjdiewornncalwe12-Sep-12 4:31
professionalfjdiewornncalwe12-Sep-12 4:31 
AnswerRe: Sieve of Eratosthenes Pin
Manfred Rudolf Bihy12-Sep-12 4:36
professionalManfred Rudolf Bihy12-Sep-12 4:36 
GeneralRe: Sieve of Eratosthenes Pin
WebMaster12-Sep-12 4:39
MemberWebMaster12-Sep-12 4:39 
GeneralRe: Sieve of Eratosthenes Pin
Manfred Rudolf Bihy12-Sep-12 4:45
professionalManfred Rudolf Bihy12-Sep-12 4:45 
GeneralRe: Sieve of Eratosthenes Pin
WebMaster12-Sep-12 4:56
MemberWebMaster12-Sep-12 4:56 
GeneralRe: Sieve of Eratosthenes Pin
Manfred Rudolf Bihy12-Sep-12 5:04
professionalManfred Rudolf Bihy12-Sep-12 5:04 
GeneralRe: Sieve of Eratosthenes Pin
Richard MacCutchan12-Sep-12 5:40
mveRichard MacCutchan12-Sep-12 5:40 
AnswerRe: Sieve of Eratosthenes PinPopular
J4amieC12-Sep-12 4:53
MemberJ4amieC12-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.
AnswerRe: Sieve of Eratosthenes Pin
Pete O'Hanlon12-Sep-12 4:54
mvaPete O'Hanlon12-Sep-12 4:54 
GeneralRe: Sieve of Eratosthenes Pin
WebMaster12-Sep-12 4:59
MemberWebMaster12-Sep-12 4:59 
GeneralRe: Sieve of Eratosthenes Pin
J4amieC12-Sep-12 5:02
MemberJ4amieC12-Sep-12 5:02 
GeneralRe: Sieve of Eratosthenes Pin
Manfred Rudolf Bihy12-Sep-12 5:06
professionalManfred Rudolf Bihy12-Sep-12 5:06 
GeneralRe: Sieve of Eratosthenes Pin
J4amieC12-Sep-12 5:07
MemberJ4amieC12-Sep-12 5:07 
GeneralRe: Sieve of Eratosthenes Pin
Pete O'Hanlon12-Sep-12 5:04
mvaPete O'Hanlon12-Sep-12 5:04 
GeneralRe: Sieve of Eratosthenes Pin
WebMaster12-Sep-12 5:16
MemberWebMaster12-Sep-12 5:16 
GeneralRe: Sieve of Eratosthenes Pin
Pete O'Hanlon12-Sep-12 5:22
mvaPete O'Hanlon12-Sep-12 5:22 
GeneralRe: Sieve of Eratosthenes Pin
J4amieC12-Sep-12 5:23
MemberJ4amieC12-Sep-12 5:23 
GeneralRe: Sieve of Eratosthenes Pin
WebMaster12-Sep-12 5:48
MemberWebMaster12-Sep-12 5:48 
GeneralRe: Sieve of Eratosthenes Pin
J4amieC12-Sep-12 5:59
MemberJ4amieC12-Sep-12 5:59 
GeneralRe: Sieve of Eratosthenes Pin
WebMaster12-Sep-12 6:11
MemberWebMaster12-Sep-12 6:11 
GeneralRe: Sieve of Eratosthenes Pin
Rage12-Sep-12 6:23
professionalRage12-Sep-12 6:23 
GeneralRe: Sieve of Eratosthenes Pin
Pete O'Hanlon12-Sep-12 6:25
mvaPete O'Hanlon12-Sep-12 6:25 
AnswerProper implementation of Sieve of Eratosthenes Pin
Clifford Nelson12-Sep-12 10:45
MemberClifford Nelson12-Sep-12 10:45 
GeneralRe: Proper implementation of Sieve of Eratosthenes Pin
WebMaster12-Sep-12 11:00
MemberWebMaster12-Sep-12 11:00 
AnswerRe: Proper implementation of Sieve of Eratosthenes Pin
Clifford Nelson12-Sep-12 11:20
MemberClifford Nelson12-Sep-12 11:20 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.