Sieve of Eratosthenes: Filtering Out Values in an Array (VBA)

K

kpark91

Well-known Member
Joined
Jul 15, 2010
Messages
1,582
Hello, I have managed get myself through the first 9 questions in Project Euler! :D

For my question #10, I am having trouble with Sieve of Eratosthenes
http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

Because I do not know how to filter out values in an array in VBA.

So, I currently have an array size of 2,000,000 (2 million)
and let's say I have some 1's and some 0's in the array.
How would I filter out 1's so that I only have an array of 0's with 'smaller size'?

Thank you in advance as always :)
kpark
 

Excel Facts

Wildcard in VLOOKUP
Use =VLOOKUP("Apple*" to find apple, Apple, or applesauce
Sort by date Sort by votes
The simplest way would be to filter out the 1's at the output stage, i.e. at the point where you display the results on the screen, print them out or transfer them to the worksheet.

If you remove all the 1's from the array and end up with only zeroes - presumably all shifted up to the beginning of the array (because you say you want to make the array smaller) - they'll no longer point to the prime numbers they belong to.

If I've misunderstood what you're asking or you don't understand what I'm saying, perhaps you could post an example of the first dozen or so elements of the array after the sieving has taken place together with an example of what you want it to look like after the 1's have been removed?
 
Upvote 0
Hello, Ruddles.
Thanks for the reply and suggestion!
I think that will be the easiest semi-programming method and I will do that :D

I wasn't expecting anybody to really read sieve of eratostheses wiki page:P

The problem was
The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.
Find the sum of all the primes below two million
Click to expand...

So, I made an array of 2,000,000.

Code: 
prime_sieve(2000000)
 
Function prime_sieve(limit As Double)
    'Returns an array of prime numbers below limit (dbl)
    Dim numArr() As Double
    ReDim numArr(limit + 1)


Since this will set all the elements inside numArr to 0's. I wanted to change elements which are divisible by the positions of the array and have the value of 0 to have value of 1. This will allow me to have all the composite numbered positions of the array to have the value of 1.


Example
Step 1) Create array
<TABLE style="WIDTH: 384pt; BORDER-COLLAPSE: collapse" border=0 cellSpacing=0 cellPadding=0 width=512><COLGROUP><COL style="WIDTH: 48pt" span=8 width=64><TBODY><TR style="HEIGHT: 15pt" height=20><TD style="BORDER-BOTTOM: #f0f0f0; BORDER-LEFT: #f0f0f0; BACKGROUND-COLOR: transparent; WIDTH: 48pt; HEIGHT: 15pt; BORDER-TOP: #f0f0f0; BORDER-RIGHT: #f0f0f0" height=20 width=64>Pos</TD><TD style="BORDER-BOTTOM: #f0f0f0; BORDER-LEFT: #f0f0f0; BACKGROUND-COLOR: transparent; WIDTH: 48pt; BORDER-TOP: #f0f0f0; BORDER-RIGHT: #f0f0f0" width=64 align=right>0</TD><TD style="BORDER-BOTTOM: #f0f0f0; BORDER-LEFT: #f0f0f0; BACKGROUND-COLOR: transparent; WIDTH: 48pt; BORDER-TOP: #f0f0f0; BORDER-RIGHT: #f0f0f0" width=64 align=right>1</TD><TD style="BORDER-BOTTOM: #f0f0f0; BORDER-LEFT: #f0f0f0; BACKGROUND-COLOR: transparent; WIDTH: 48pt; BORDER-TOP: #f0f0f0; BORDER-RIGHT: #f0f0f0" width=64 align=right>2</TD><TD style="BORDER-BOTTOM: #f0f0f0; BORDER-LEFT: #f0f0f0; BACKGROUND-COLOR: transparent; WIDTH: 48pt; BORDER-TOP: #f0f0f0; BORDER-RIGHT: #f0f0f0" width=64 align=right>3</TD><TD style="BORDER-BOTTOM: #f0f0f0; BORDER-LEFT: #f0f0f0; BACKGROUND-COLOR: transparent; WIDTH: 48pt; BORDER-TOP: #f0f0f0; BORDER-RIGHT: #f0f0f0" width=64 align=right>4</TD><TD style="BORDER-BOTTOM: #f0f0f0; BORDER-LEFT: #f0f0f0; BACKGROUND-COLOR: transparent; WIDTH: 48pt; BORDER-TOP: #f0f0f0; BORDER-RIGHT: #f0f0f0" width=64 align=right>5</TD><TD style="BORDER-BOTTOM: #f0f0f0; BORDER-LEFT: #f0f0f0; BACKGROUND-COLOR: transparent; WIDTH: 48pt; BORDER-TOP: #f0f0f0; BORDER-RIGHT: #f0f0f0" width=64 align=right>6</TD></TR><TR style="HEIGHT: 15pt" height=20><TD style="BORDER-BOTTOM: #f0f0f0; BORDER-LEFT: #f0f0f0; BACKGROUND-COLOR: transparent; HEIGHT: 15pt; BORDER-TOP: #f0f0f0; BORDER-RIGHT: #f0f0f0" height=20>Val</TD><TD style="BORDER-BOTTOM: #f0f0f0; BORDER-LEFT: #f0f0f0; BACKGROUND-COLOR: transparent; BORDER-TOP: #f0f0f0; BORDER-RIGHT: #f0f0f0" align=right>0</TD><TD style="BORDER-BOTTOM: #f0f0f0; BORDER-LEFT: #f0f0f0; BACKGROUND-COLOR: transparent; BORDER-TOP: #f0f0f0; BORDER-RIGHT: #f0f0f0" align=right>0</TD><TD style="BORDER-BOTTOM: #f0f0f0; BORDER-LEFT: #f0f0f0; BACKGROUND-COLOR: transparent; BORDER-TOP: #f0f0f0; BORDER-RIGHT: #f0f0f0" align=right>0</TD><TD style="BORDER-BOTTOM: #f0f0f0; BORDER-LEFT: #f0f0f0; BACKGROUND-COLOR: transparent; BORDER-TOP: #f0f0f0; BORDER-RIGHT: #f0f0f0" align=right>0</TD><TD style="BORDER-BOTTOM: #f0f0f0; BORDER-LEFT: #f0f0f0; BACKGROUND-COLOR: transparent; BORDER-TOP: #f0f0f0; BORDER-RIGHT: #f0f0f0" align=right>0</TD><TD style="BORDER-BOTTOM: #f0f0f0; BORDER-LEFT: #f0f0f0; BACKGROUND-COLOR: transparent; BORDER-TOP: #f0f0f0; BORDER-RIGHT: #f0f0f0" align=right>0</TD><TD style="BORDER-BOTTOM: #f0f0f0; BORDER-LEFT: #f0f0f0; BACKGROUND-COLOR: transparent; BORDER-TOP: #f0f0f0; BORDER-RIGHT: #f0f0f0" align=right>0</TD></TR></TBODY></TABLE>

Step 2) Change all the composite numbered positions' values to 1 (exceptions:0,1) through iterations
<TABLE style="WIDTH: 384pt; BORDER-COLLAPSE: collapse" border=0 cellSpacing=0 cellPadding=0 width=512><COLGROUP><COL style="WIDTH: 48pt" span=8 width=64><TBODY><TR style="HEIGHT: 15pt" height=20><TD style="BORDER-BOTTOM: #f0f0f0; BORDER-LEFT: #f0f0f0; BACKGROUND-COLOR: transparent; WIDTH: 48pt; HEIGHT: 15pt; BORDER-TOP: #f0f0f0; BORDER-RIGHT: #f0f0f0" height=20 width=64>Pos</TD><TD style="BORDER-BOTTOM: #f0f0f0; BORDER-LEFT: #f0f0f0; BACKGROUND-COLOR: transparent; WIDTH: 48pt; BORDER-TOP: #f0f0f0; BORDER-RIGHT: #f0f0f0" width=64 align=right>0</TD><TD style="BORDER-BOTTOM: #f0f0f0; BORDER-LEFT: #f0f0f0; BACKGROUND-COLOR: transparent; WIDTH: 48pt; BORDER-TOP: #f0f0f0; BORDER-RIGHT: #f0f0f0" width=64 align=right>1</TD><TD style="BORDER-BOTTOM: #f0f0f0; BORDER-LEFT: #f0f0f0; BACKGROUND-COLOR: transparent; WIDTH: 48pt; BORDER-TOP: #f0f0f0; BORDER-RIGHT: #f0f0f0" width=64 align=right>2</TD><TD style="BORDER-BOTTOM: #f0f0f0; BORDER-LEFT: #f0f0f0; BACKGROUND-COLOR: transparent; WIDTH: 48pt; BORDER-TOP: #f0f0f0; BORDER-RIGHT: #f0f0f0" width=64 align=right>3</TD><TD style="BORDER-BOTTOM: #f0f0f0; BORDER-LEFT: #f0f0f0; BACKGROUND-COLOR: transparent; WIDTH: 48pt; BORDER-TOP: #f0f0f0; BORDER-RIGHT: #f0f0f0" width=64 align=right>4</TD><TD style="BORDER-BOTTOM: #f0f0f0; BORDER-LEFT: #f0f0f0; BACKGROUND-COLOR: transparent; WIDTH: 48pt; BORDER-TOP: #f0f0f0; BORDER-RIGHT: #f0f0f0" width=64 align=right>5</TD><TD style="BORDER-BOTTOM: #f0f0f0; BORDER-LEFT: #f0f0f0; BACKGROUND-COLOR: transparent; WIDTH: 48pt; BORDER-TOP: #f0f0f0; BORDER-RIGHT: #f0f0f0" width=64 align=right>6</TD></TR><TR style="HEIGHT: 15pt" height=20><TD style="BORDER-BOTTOM: #f0f0f0; BORDER-LEFT: #f0f0f0; BACKGROUND-COLOR: transparent; HEIGHT: 15pt; BORDER-TOP: #f0f0f0; BORDER-RIGHT: #f0f0f0" height=20>Val</TD><TD style="BORDER-BOTTOM: #f0f0f0; BORDER-LEFT: #f0f0f0; BACKGROUND-COLOR: transparent; BORDER-TOP: #f0f0f0; BORDER-RIGHT: #f0f0f0" align=right>0</TD><TD style="BORDER-BOTTOM: #f0f0f0; BORDER-LEFT: #f0f0f0; BACKGROUND-COLOR: transparent; BORDER-TOP: #f0f0f0; BORDER-RIGHT: #f0f0f0" align=right>0</TD><TD style="BORDER-BOTTOM: #f0f0f0; BORDER-LEFT: #f0f0f0; BACKGROUND-COLOR: transparent; BORDER-TOP: #f0f0f0; BORDER-RIGHT: #f0f0f0" align=right>0</TD><TD style="BORDER-BOTTOM: #f0f0f0; BORDER-LEFT: #f0f0f0; BACKGROUND-COLOR: transparent; BORDER-TOP: #f0f0f0; BORDER-RIGHT: #f0f0f0" align=right>0</TD><TD style="BORDER-BOTTOM: #f0f0f0; BORDER-LEFT: #f0f0f0; BACKGROUND-COLOR: transparent; BORDER-TOP: #f0f0f0; BORDER-RIGHT: #f0f0f0" align=right>1</TD><TD style="BORDER-BOTTOM: #f0f0f0; BORDER-LEFT: #f0f0f0; BACKGROUND-COLOR: transparent; BORDER-TOP: #f0f0f0; BORDER-RIGHT: #f0f0f0" align=right>0</TD><TD style="BORDER-BOTTOM: #f0f0f0; BORDER-LEFT: #f0f0f0; BACKGROUND-COLOR: transparent; BORDER-TOP: #f0f0f0; BORDER-RIGHT: #f0f0f0" align=right>1</TD></TR></TBODY></TABLE>

Step 3) Filter out the array's elements that have value of 1 and change the elements' values to the position numbers at the same time (through iterations) except for 0, 1
<TABLE style="WIDTH: 288pt; BORDER-COLLAPSE: collapse" border=0 cellSpacing=0 cellPadding=0 width=384><COLGROUP><COL style="WIDTH: 48pt" span=6 width=64><TBODY><TR style="HEIGHT: 15pt" height=20><TD style="BORDER-BOTTOM: #f0f0f0; BORDER-LEFT: #f0f0f0; BACKGROUND-COLOR: transparent; WIDTH: 48pt; HEIGHT: 15pt; BORDER-TOP: #f0f0f0; BORDER-RIGHT: #f0f0f0" height=20 width=64>Pos</TD><TD style="BORDER-BOTTOM: #f0f0f0; BORDER-LEFT: #f0f0f0; BACKGROUND-COLOR: transparent; WIDTH: 48pt; BORDER-TOP: #f0f0f0; BORDER-RIGHT: #f0f0f0" width=64 align=right>0</TD><TD style="BORDER-BOTTOM: #f0f0f0; BORDER-LEFT: #f0f0f0; BACKGROUND-COLOR: transparent; WIDTH: 48pt; BORDER-TOP: #f0f0f0; BORDER-RIGHT: #f0f0f0" width=64 align=right>1</TD><TD style="BORDER-BOTTOM: #f0f0f0; BORDER-LEFT: #f0f0f0; BACKGROUND-COLOR: transparent; WIDTH: 48pt; BORDER-TOP: #f0f0f0; BORDER-RIGHT: #f0f0f0" width=64 align=right>2</TD><TD style="BORDER-BOTTOM: #f0f0f0; BORDER-LEFT: #f0f0f0; BACKGROUND-COLOR: transparent; WIDTH: 48pt; BORDER-TOP: #f0f0f0; BORDER-RIGHT: #f0f0f0" width=64 align=right>3</TD><TD style="BORDER-BOTTOM: #f0f0f0; BORDER-LEFT: #f0f0f0; BACKGROUND-COLOR: transparent; WIDTH: 48pt; BORDER-TOP: #f0f0f0; BORDER-RIGHT: #f0f0f0" width=64 align=right>4</TD></TR><TR style="HEIGHT: 15pt" height=20><TD style="BORDER-BOTTOM: #f0f0f0; BORDER-LEFT: #f0f0f0; BACKGROUND-COLOR: transparent; HEIGHT: 15pt; BORDER-TOP: #f0f0f0; BORDER-RIGHT: #f0f0f0" height=20>Val</TD><TD style="BORDER-BOTTOM: #f0f0f0; BORDER-LEFT: #f0f0f0; BACKGROUND-COLOR: transparent; BORDER-TOP: #f0f0f0; BORDER-RIGHT: #f0f0f0" align=right>0</TD><TD style="BORDER-BOTTOM: #f0f0f0; BORDER-LEFT: #f0f0f0; BACKGROUND-COLOR: transparent; BORDER-TOP: #f0f0f0; BORDER-RIGHT: #f0f0f0" align=right>0</TD><TD style="BORDER-BOTTOM: #f0f0f0; BORDER-LEFT: #f0f0f0; BACKGROUND-COLOR: transparent; BORDER-TOP: #f0f0f0; BORDER-RIGHT: #f0f0f0" align=right>2</TD><TD style="BORDER-BOTTOM: #f0f0f0; BORDER-LEFT: #f0f0f0; BACKGROUND-COLOR: transparent; BORDER-TOP: #f0f0f0; BORDER-RIGHT: #f0f0f0" align=right>3</TD><TD style="BORDER-BOTTOM: #f0f0f0; BORDER-LEFT: #f0f0f0; BACKGROUND-COLOR: transparent; BORDER-TOP: #f0f0f0; BORDER-RIGHT: #f0f0f0" align=right>5</TD></TR></TBODY></TABLE>

End of Example

So, basically, I want to be able to 'resize' everytime with every iteration in Step 2. (Modulus 2.. Modulus 3... Modulus 5... and onwards with the prime numbers).
But now that I think about it, I think I may be able to do it but any help is appreciated!
 
Upvote 0
Here's one way, using a collection:
Code: 
Sub Sieve()
    Const n         As Long = 100000 ' numbers to test
    Dim colCand     As Collection   ' candidates
    Dim aiPrim()    As Long         ' primes for output
    Dim iPrim       As Long         ' a prime
    Dim nPrim       As Long         ' running count of primes
    Dim i           As Long         ' scratch index
 
    Set colCand = New Collection
    ReDim aiPrim(1 To 1.1 * n / (Log(n) - 2)) ' high estimate for nPrim
 
    ' initialize candidates
    For i = 2 To n
        colCand.Add Item:=i, Key:=CStr(i)
    Next i
 
    ' we'll be trying to delete numbers in colCand that were already deleted
    On Error Resume Next
 
    Do While colCand.Count
        ' first number in colCand is a prime
        nPrim = nPrim + 1
        iPrim = colCand(1)
        aiPrim(nPrim) = iPrim
        colCand.Remove 1
 
        ' remove all multiples
        For i = 2 To n \ iPrim
            colCand.Remove CStr(i * iPrim)
        Next i
    Loop
 
    'list 'em
    Range("A1").Resize(nPrim).Value = WorksheetFunction.Transpose(aiPrim)
    Beep
End Sub
 
Last edited:
Upvote 0
shg
Whoaaaa. I don't understand it at all!! lollll
Sir... I want you as my teacher haha.

What does 1.1 * n / (Log(n) - 2) mean??
and what' a collection? O_o
From my research (poor), it seems like an array. How come you chose collection over array?

Thank you very much :)
 
Upvote 0
This line:

Code: 
    ReDim aiPrim(1 To 1.1 * n / (Log(n) - 2))
should be

Code: 
    ReDim aiPrim(1 To n / (Log(n) - 2))
 
Upvote 0
Ahhhhh now I understand it!! You're too awesome!! xD

Now I shall make it mine and do it with array :D

Thank you for the hints :D
 
Upvote 0
kpark91 said:
Step 1) Create array
Step 2) Change all the composite numbered positions' values to 1 (exceptions:0,1) through iterations
Step 3) Filter out the array's elements that have value of 1 and change the elements' values to the position numbers at the same time (through iterations) except for 0, 1
Click to expand...
Aaah... cunning! Okay, I've written a subroutine which will take an array, shuffle all the zeroes to the start of the array and change them to their original position, then resize the array to fit those remaining entries.

Paste this into a new general code module:-
Code: 
Option Explicit
 
Public Sub ShuffleArray(ByRef arr As Variant)
 
  Dim i As Long
  Dim j As Long
  
  arr(1) = 1
  arr(2) = 2
  arr(3) = 3
  i = 3
  For j = 3 To UBound(arr)
    If arr(j) = 0 Then
      i = i + 1
      arr(i) = j
      arr(j) = 1
    End If
  Next j
  
  ReDim Preserve arr(i)
 
End Sub
Then at the point in your code where your array of 2000000 is populated, call my subroutine as follows:-
Code: 
Call ShuffleArray([I]arrayname[/I])

Is that what you're after?
 
Upvote 0
yes it is!!

So, basically to resize something without deleting the elements is to use
Code: 
ReDime Preserve
?

Thank you very much for your help :)
kpark
 
Upvote 0
You must log in or register to reply here.

Similar threads

J
  • Solved
Search/Filter a Spreadsheet by User Entered Value
Replies
3
Views
201
jbennett01
J
S
  • Question Question
VBA - Filter a class array based on class function
Replies
1
Views
182
RoryA
RoryA
R
  • Question Question
Spill array that only shows rows that have value in certain cells
Replies
1
Views
151
Alex Blakenburg
A
B
  • Solved
Textjoin and Filter using VBA
Replies
7
Views
335
BritsBlitz
B
P
  • Solved
Lambda and custom sequence with interference of string
Replies
3
Views
251
StephenCrump
S

Forum statistics

Threads
1,224,586
Messages
6,179,729
Members
452,939
Latest member
WCrawford

Share this page

We've detected that you are using an adblocker.

We have a great community of people providing Excel help here, but the hosting costs are enormous. You can help keep this site running by allowing ads on MrExcel.com.
Allow Ads at MrExcel

Which adblocker are you using?

Disable AdBlock

Follow these easy steps to disable AdBlock

1)Click on the icon in the browser’s toolbar.
2)Click on the icon in the browser’s toolbar.
2)Click on the "Pause on this site" option.
Go back

Disable AdBlock Plus

Follow these easy steps to disable AdBlock Plus

1)Click on the icon in the browser’s toolbar.
2)Click on the toggle to disable it for "mrexcel.com".
Go back

Disable uBlock Origin

Follow these easy steps to disable uBlock Origin

1)Click on the icon in the browser’s toolbar.
2)Click on the "Power" button.
3)Click on the "Refresh" button.
Go back

Disable uBlock

Follow these easy steps to disable uBlock

1)Click on the icon in the browser’s toolbar.
2)Click on the "Power" button.
3)Click on the "Refresh" button.
Go back
Back
Top