By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
435,446 Members | 3,120 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 435,446 IT Pros & Developers. It's quick & easy.

Help with algorithm of Sieve of Eratosthenes

P: n/a
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...

Apr 10 '07 #1
Share this Question
Share on Google+
4 Replies


P: n/a
On Apr 10, 10:05 am, "knu...@gmail.com" <knu...@gmail.comwrote:
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

Apr 10 '07 #2

P: n/a
On Apr 10, 3:46 pm, "rowe_newsgroups" <rowe_em...@yahoo.comwrote:
On Apr 10, 10:05 am, "knu...@gmail.com" <knu...@gmail.comwrote:
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

Apr 10 '07 #3

P: n/a
On Apr 10, 12:57 pm, "knu...@gmail.com" <knu...@gmail.comwrote:
On Apr 10, 3:46 pm, "rowe_newsgroups" <rowe_em...@yahoo.comwrote:
On Apr 10, 10:05 am, "knu...@gmail.com" <knu...@gmail.comwrote:
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/algori...imenumbers.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

Apr 10 '07 #4

P: n/a
On Apr 10, 6:47 pm, "rowe_newsgroups" <rowe_em...@yahoo.comwrote:
On Apr 10, 12:57 pm, "knu...@gmail.com" <knu...@gmail.comwrote:
On Apr 10, 3:46 pm, "rowe_newsgroups" <rowe_em...@yahoo.comwrote:
On Apr 10, 10:05 am, "knu...@gmail.com" <knu...@gmail.comwrote:
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/algori...imenumbers.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.

Apr 10 '07 #5

This discussion thread is closed

Replies have been disabled for this discussion.