Results 1 to 2 of 2

Thread: Sieve of Eratosthenes

Threaded View

  1. Nov 18th, 2005, 06:38 AM #1
    x-ice
    x-ice is offline

    Thread Starter
    Fanatic Member x-ice's Avatar
    Join Date
    Mar 2004
    Location
    UK
    Posts
    671

    Resolved Sieve of Eratosthenes

    Code:
    Eratosthenes(n) {
  a[1] := 0                          
  for i := 2 to n do a[i] := 1
  p := 2
  while p2  <  n do {
    j := p2
    while (j  <  n) do {             
      a[j] := 0
      j := j+p
    }
    repeat p := p+1 until a[p] = 1   
  }
  return(a)
}
    What is n? What would be the formula to work out the complexity of this algorithm?
    Last edited by x-ice; Feb 25th, 2007 at 07:24 PM.
    Reply With Quote Reply With Quote
« Previous Thread | Next Thread »

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  

Forum Rules


Click Here to Expand Forum to Full Width