Click here to Skip to main content
15,886,137 members
Please Sign up or sign in to vote.
2.00/5 (2 votes)
See more:
It takes me about 40 seconds to go through 100000.
I killed to process for 1 million because it was taking so long.
I'm running a FX6100 running @ 4.5Ghz and only using 15%.
I have thought about running multiple threads and done just a wee bit of research on it
but I have never done that. I'm just wondering if there are any suggestions for making this code more efficient.

Thanks in advance. :)

VB
Private Sub btnGo_Click(sender As Object, e As EventArgs) Handles btnGo.Click
      Dim j As Integer = 1
      Dim c As Integer
      Dim max As Integer = 100000
      For I As Integer = 1 To max
          j = I
          c = 0
          Do
              If I Mod j = 0 Then
                  c += 1
                  If c > 2 Then
                      Exit Do
                  End If
              End If
                  j -= 1
          Loop Until j = 0
          If c = 2 Then
              lbxSquare.Items.Add(I.ToString())
          End If
          If I = max Then
              lbxSquare.Items.Add("There are " & lbxSquare.Items.Count.ToString() & " prime numbers")
          End If
      Next
  End Sub
Posted
Updated 12-Jul-14 21:46pm
v3

The best way is to use the Sieve of Eratosthenes as described in Finding prime numbers[^].
 
Share this answer
 
Comments
Dave Kreskowiak 13-Jul-14 11:21am    
Get's my 5. I used that algorithm to implement my sieve when I did a bunch of the Project Euler problems. Millions of primes generated in milliseconds.
Richard MacCutchan 13-Jul-14 11:30am    
Thanks, but Kenneth deserves the points.
Dave Kreskowiak 13-Jul-14 11:33am    
I gave him the points too!

After looking at the bottom of that article, I'm kind of interested in taking a crack at converting the C code for the Sieve of Atkin he linked to C#. When I have time...
Member 10942607 13-Jul-14 22:00pm    
Yeah, I should have thought about that. :(
After I posted I was thinking of including all the rules of division,
but didn't even think of going the other way and doing larger factor.
Seems I totally missed the ball on that one.
Maciej Los 6-Nov-14 13:01pm    
+5!
Here is a solution written in C#.
It takes less than 20 milliseconds to find all the prime numbers up to 100000. About 5 seconds to find all up to 10 millions.
My PC is an AMD FX6100 @ 3.3G.

C#
private static void Main(string[] args)
{
    var sw = Stopwatch.StartNew();
    var collection = new List<int>();

    //assume "2" as known, so let's start from 3
    for (int i = 3; i < 100000; i += 2)
    {
        //no reason to scan over the square-root of the integer under test
        double root = Math.Sqrt(i);

        bool found = false;
        for (int k = 0, count = collection.Count; k < count; k++)
        {
            int divisor;
            if ((divisor = collection[k]) > root)
            {
                //no futher reason to scan
                break;
            }
            else if ((i % divisor) == 0)
            {
                //found a divisor
                found = true;
                break;
            }
        }

        if (found == false)
        {
            //no divisor found, so add yet another prime number!
            collection.Add(i);
        }
    }

    //insert the known "2" as the very first
    collection.Insert(0, 2);

    Console.WriteLine("time=" + sw.ElapsedMilliseconds);
    Console.WriteLine("count=" + collection.Count);

    //display the entire collection (a text file on disk would be better, though)
    //foreach (int num in collection)
    //{
    //    Console.Write("{0}; ",num);
    //}

    //wait for a user keypress
    Console.ReadKey();
}
 
Share this answer
 
Comments
Dave Kreskowiak 13-Jul-14 11:19am    
It's good, but not fast enough for my tastes.

I wrote an implementation of the Sieve of Eratosthenes that can generate a list of primes, up to 10,000,000 in under 170 milliseconds, on a 4 year old machine.
try below logic..
VB
Dim p, n, i As Integer
p = 1
Print "Prime Numbers are : "
For n = 1 To 100
For i = 2 To n – 1
If n Mod i = 0 Then
p = 0
Exit For
Else
p = 1
End If

Next
If p = 1 Then
Print n
End If

Next
 
Share this answer
 
Comments
Dave Kreskowiak 13-Jul-14 11:06am    
That's really no different than what he has already. That's also the slowest way to generate a list of primes.
nilesh sawardekar 13-Jul-14 11:19am    
i told him to try..did not mentioned anywhere that its your solution.
Richard MacCutchan 13-Jul-14 11:29am    
The point is that this is the same as the OP has already tried, and it is not a good solution. See the article that I linked to in my answer above.
Dave Kreskowiak 13-Jul-14 11:33am    
I said that your solution was no different than the code he already has. It's not faster than what he's got and therefor not an answer to the question.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900