Re: Help with algorithm of Sieve of Eratosthenes

Tech-Archive recommends: Repair Windows Errors & Optimize Windows Performance

On Apr 10, 12:57 pm, "knu...@xxxxxxxxx" <knu...@xxxxxxxxx> wrote:
On Apr 10, 3:46 pm, "rowe_newsgroups" <rowe_em...@xxxxxxxxx> wrote:



On Apr 10, 10:05 am, "knu...@xxxxxxxxx" <knu...@xxxxxxxxx> wrote:

Hey everyone....
I would appreciate any type of help if anyone could explain me how to
translate this algorithm to Visual Basic, im still learning and i
would appreciate this algorithm to my prime number program, which
lists primes but can use different algorithms.

// arbitrary search limit
limit ← 1.000.000

// assume all numbers are prime at first
is_prime(i) ← true, i ∈ [2, limit]

for n in [2, √limit]:
if is_prime(n):
// eliminate multiples of each prime,
// starting with its square
is_prime(i) ← false, i ∈ {n², n²+n, n²+2n, ..., limit}

for n in [2, limit]:
if is_prime(n): print n

this is listed in wikipedia, and there is also another form which i
find even more complicated. but i dont understand how can i eliminate
multiples and all of the rest, if anyone could point me to an easy
explanation.

Thanks in advance...

http://www.physicsforums.com/showthread.php?t=9298

Let me know if that thread doesn't answer your question and I'll take
another look.

Thanks,

Seth Rowe

If anyone else could give another hint, all things that are said in
that forum are kinda advanced to me..its all about datasets and
statusbars...i just wantend something to print prime numbers in a
textbox, using the sieve of eratosthenes...

thanks

Here's another article - I believe it uses the Sieve of Eratosthenes:

http://www.codeproject.com/cs/algorithms/highspeed_primenumbers.asp

I also took the liberty of translating the code into VB for you - I
didn't test the algorithm completely though so be careful:

Sub Main()

' Change this for a different cutoff
Dim topNumber As Integer = 1000000
Dim numbers As BitArray = New BitArray(topNumber, True)

For i As Integer = 2 To topNumber - 1
If numbers(i) Then
For j As Integer = i * 2 To topNumber - 1 Step i
numbers(j) = False
Next
End If
Next

Dim primes As Integer = 0

For i As Integer = 1 To topNumber - 1
If numbers(i) Then
primes += 1
' Console.WriteLine(i.ToString())
End If
Next

Console.WriteLine()
Console.WriteLine("{0} out of {1} prime numbers found.",
primes, topNumber)
Console.Read()
End Sub

Thanks,

Seth Rowe

.

Relevant Pages

  • Re: Any way to take a word as input from stdin ?
    ... snip ... ... If he wants to use a C++ algorithm as illustration he ... His question was basically about how to translate the C++ algorithm to ... So what you're saying is that he must answer his own question ...
    (comp.lang.c)
  • Re: Any way to take a word as input from stdin ?
    ... snip ... ... If he wants to use a C++ algorithm as illustration he ... His question was basically about how to translate the C++ algorithm to ... So what you're saying is that he must answer his own question ...
    (comp.lang.c)
  • Re: Help with algorithm of Sieve of Eratosthenes
    ... translate this algorithm to Visual Basic, ... Dim topNumber As Integer = 1000000 ... Dim numbers As BitArray = New BitArray ...
    (microsoft.public.dotnet.languages.vb)
  • Re: translating imperative pseudocode to functional
    ... In general graph algorithms aren't easy ... to translate into a purely functional language. ... A quick look at the contents showed me that it implements an algorithm ... > i have the following pseudocode algorithm for finding the largest set ...
    (comp.lang.functional)
  • RE: UDF to Calculate YTM
    ... But I think you fundamentally misunderstand the algorithm. ... the MoneyChimp pop-up calculator for the example in the aritcle (price $950, ... Dim hi As Double, lo As Double, r0 As Double ... On Error GoTo myError ...
    (microsoft.public.excel.programming)