Printable View
the attached project has two methods of calculating primes. the one using linq appears to run faster but... it is noticeable only when calculating large number of primes i.e. the primes between 1 and 1,000,000. i don't understand the odd behavior of the linq method.
Attachment 69619
That's a cool way of utilizing LINQ. I never would have thought of that.
One thing I notice is that when you're using the non-LINQ method you 'cross-out' some non-primes repeatedly. For example, when you start off with 2 you cross out 2, 4, 6, 8, ... by assigning the corresponding index in thePrimes to -1. But when you go by 3, you will cross out 3, 6, 9, 12, 15, 18 ... half of which were already crossed out when you did the multiples of 2. This is true for other numbers too. With the LINQ method once a number is removed as a prime it's gone for good.
We need to write the non-LINQ method in a way that doesn't recheck numbers that have already been determined to be nonprime.
EDIT: I didn't even ask but I assumed that the odd behavior was that the LINQ method ran significantly faster. Is that what you meant?
on my pc the linq method, according to the stopwatch, ran significantly faster, but the overall time was significantly slower. that was what i found to be odd.
i also noticed that linq code produced:
2,3,5,7 for the prime numbers from 1 - 6
I had the same experience:
No LINQ
Execution - 70ms
Total Time - 2s
LINQ
Execution - 12ms
Total Time 15s
@max - that is what i saw.
The loss of speed happens when you collapse the IEnumerable in the line:
Label1.Text = searchnumbers.Count.ToString("N0")
Remember, LINQ uses lambdas to define itself. Lambdas are just meta-code until you evaluate it.
All that LINQ is essentially setting up the structure of meta code to be processed. The actual processing and filling of the IEnumerable doesn't come until you do something with it.
as a function
Code:'Sieve of Eratosthenes
'http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
'1. Create a contiguous list of numbers from two to some highest number n.
'2. Strike out from the list all multiples of two (4, 6, 8 etc.).
'3. The list's next number that has not been struck out is a prime number.
'4. Strike out from the list all multiples of the number you identified in the previous step.
'5. Repeat steps 3 and 4 until you reach a number that is greater than the square root of n (the highest number in the list).
'6. All the remaining numbers in the list are prime.
Private Function Sieve_of_Eratosthenes(ByVal MaxNum As Integer) As List(Of Integer)
'tested to MaxNum = 10,000,000 - on 1.8Ghz Laptop it took 1.4 seconds
Dim thePrimes As New List(Of Integer)
Dim toNum As Integer = MaxNum, stpw As New Stopwatch
If toNum > 1 Then 'the first prime is 2
stpw.Start()
thePrimes.Capacity = toNum 'size the list
Dim idx As Integer
Dim stopAT As Integer = CInt(Math.Sqrt(toNum) + 1)
'1. Create a contiguous list of numbers from two to some highest number n.
'2. Strike out from the list all multiples of 2, 3, 5.
For idx = 0 To toNum
If idx > 5 Then
If idx Mod 2 <> 0 _
AndAlso idx Mod 3 <> 0 _
AndAlso idx Mod 5 <> 0 Then thePrimes.Add(idx) Else thePrimes.Add(-1)
Else
thePrimes.Add(idx)
End If
Next
'mark 0,1 and 4 as non-prime
thePrimes(0) = -1
thePrimes(1) = -1
thePrimes(4) = -1
Dim aPrime, startAT As Integer
idx = 7 'starting at 7 check for primes and multiples
Do
'3. The list's next number that has not been struck out is a prime number.
'4. Strike out from the list all multiples of the number you identified in the previous step.
'5. Repeat steps 3 and 4 until you reach a number that is greater than the square root of n (the highest number in the list).
If thePrimes(idx) <> -1 Then ' if equal to -1 the number is not a prime
'not equal to -1 the number is a prime
aPrime = thePrimes(idx)
'get rid of multiples
startAT = aPrime * aPrime
For mltpl As Integer = startAT To thePrimes.Count - 1 Step aPrime
If thePrimes(mltpl) <> -1 Then thePrimes(mltpl) = -1
Next
End If
idx += 2 'increment index
Loop While idx < stopAT
'6. All the remaining numbers in the list are prime.
thePrimes = thePrimes.FindAll(Function(i As Integer) i <> -1)
stpw.Stop()
Debug.WriteLine(stpw.ElapsedMilliseconds)
End If
Return thePrimes
End Function
i commented out the count. now it seems that this has the same issue
Code:ListBox1.BeginUpdate()
For Each i As Integer In searchnumbers
ListBox1.Items.Add(i)
Next
ListBox1.EndUpdate()
On my machine
NO LINQ
Execution Time: 25 ms
Total Time: 1.1 seconds
LINQ
Execution Time: 76 ms
Total Time: 7.8 seconds
EDIT: Brain Fart (not enough coffee numbers were reversed, I just fixed it)