Help with algorithm of Sieve of Eratosthenes

[knuxus]

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...

 

[rowe_newsgroups]

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

 

[knuxus]

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

 

[rowe_newsgroups]

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

 

[knuxus]

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

Thank you! This is very helpful.