Proper implementation of Sieve of Eratosthenes - C# Discussion Boards

Pete O'Hanlon12-Sep-12 5:22

Pete O'Hanlon

12-Sep-12 5:22

I understood your code perfectly. I can't help it if I'm able to understand algorithms better than you can; it's called age, wisdom and experience.

What I needed you to do is actually go and read the algorithm itself. The sieve is not brute force - your code is. I'm guessing that this is a homework assignment for you, so I'm not going to give you the code - but the pseudocode in the wikipedia article articulates the solution perfectly. Perhaps if you actually tried that algorithm rather then you'd see why I'm saying what it is.

Meysam Tolouee wrote:
for (int p = 0; p < numbers.Count - 1; p++)

You don't need to go all the way through to the end of the list. You only need to go to the square root of n.

Meysam Tolouee wrote:
if (numbers[j].Value % numbers[p].Value == 0)

Not needed. The sieve doesn't require this test.

*pre-emptive celebratory nipple tassle jiggle* - Sean Ewington

"Mind bleach! Send me mind bleach!" - Nagy Vilmos

CodeStash - Online Snippet Management | My blog | MoXAML PowerToys | Mole 2010 - debugging made easier

J4amieC12-Sep-12 5:23

J4amieC

12-Sep-12 5:23

See how point 2 is different from your implementation, and how the description of point 3 is TOTALLY different from your implementation

By way of example I mocked up 2 implementations. The first uses your code:

static void Brute(int max)
{
    var numbers = new List<Number>();
    for (int i = 2; i < max; i++)
        numbers.Add(new Number(i));

    var sw = new Stopwatch();
    sw.Start();
    for (int i = 0; i < numbers.Count - 1; i++)
        if (numbers[i].IsPrime)
            for (int j = i + 1; j < numbers.Count - 1; j++)
                if (numbers[j].Value % numbers[i].Value == 0)
                    numbers[j].IsPrime = false;

    sw.Stop();
    Console.WriteLine("Brute: {0}ms",sw.ElapsedMilliseconds);
}

I reduced it to only going to 200000, as it took too long to go all the way to 20000000 for the purpose of this demo:

Result:

Brute: 152009ms

Then I mocked up a very quick Sieve implementation without the enhancements that can be made (described in the wiki article)

-- Code example removed. If this is homework, im not doing it for you.

Result:

Sieve:15ms

The proof, as they say, is in the pudding. In this case Sieve pudding is ready just a little bit quicker

WebMaster12-Sep-12 5:48

WebMaster

12-Sep-12 5:48

It is not my homework.

I am solving this.[^]

Also I didn't down vote any of the post in this forum.

Meysam

J4amieC12-Sep-12 5:59

J4amieC

12-Sep-12 5:59

Well I can tell you the answer (142913828922 calculated in 386ms), but you should definately try to work out the right algo yourself, its a good learning excercise.

By the way, your original code goes to 20 million, whereas the problem you're solving asks for 2 million.

WebMaster12-Sep-12 6:11

WebMaster

12-Sep-12 6:11

It is not important for me to know the answer.

I want to find out the best algorithm, and you are not going to help me.
Thanks anyway.

Meysam

Rage12-Sep-12 6:23

Rage

12-Sep-12 6:23

Meysam Tolouee wrote:
nd you are not going to help me.

What the hell do you want him to do ? He has told you in about every possible way how you should improve your code, starting by implementing the algorithm correctly.

~RaGE();

I think words like 'destiny' are a way of trying to find order where none exists. - Christian Graus
Do not feed the troll ! - Common proverb

Proper implementation of Sieve of Eratosthenes

Pete O'Hanlon12-Sep-12 6:25

Pete O'Hanlon

12-Sep-12 6:25

We have told you where the algorithm is. You just haven't used it. Seriously, put your preconceptions to one side and take a look at that wiki page. Read the explanation and then carefully read the algorithm presented there. Then try writing it fresh. You'll be amazed at the difference.

*pre-emptive celebratory nipple tassle jiggle* - Sean Ewington

"Mind bleach! Send me mind bleach!" - Nagy Vilmos

CodeStash - Online Snippet Management | My blog | MoXAML PowerToys | Mole 2010 - debugging made easier

Clifford Nelson12-Sep-12 10:45

Clifford Nelson

12-Sep-12 10:45

You made a big error in the algorithm as stated above. Also you add work with instantiating classes (struct probably better).

private static bool[] _numbers;

static void Main(string[] args)
{
    var sw = new Stopwatch();
    sw.Start();
    Run();
    sw.Stop();
    Console.WriteLine("Milliseconds run: " + sw.ElapsedMilliseconds);
    Console.WriteLine("Primes: " + _numbers.Count(i => i));
    Console.ReadLine();
}

private static void Run()
{
    const int count = 2000000;
    _numbers = new bool[count];
    for (int i = 2; i < count; i++)
        _numbers[i] = true;

    int baseCounter = 1;

    while (baseCounter < count)
    {
        do
        {
            baseCounter++;
            if (baseCounter == count) return;
        } while (!_numbers[baseCounter]);

        int counter = baseCounter << 1;
        while (counter < count)
        {
            _numbers[counter] = false;
            counter += baseCounter;
        }
    }

WebMaster12-Sep-12 11:00

WebMaster

12-Sep-12 11:00

I want the sum of prime numbers not count of them!

long sum = 0;
for (int i = 0; i < _numbers.Length - 1; i++)
{
   if (_numbers[i])
      sum += i;
}

Thank you for your time.

Meysam

modified 12-Sep-12 17:12pm.

Clifford Nelson12-Sep-12 11:20

Clifford Nelson

12-Sep-12 11:20

If you want the sum or primes then:

static void Main(string[] args)
    {
        var sw = new Stopwatch();
        sw.Start();
        Run();
        sw.Stop();
        Console.WriteLine("Milliseconds run: " + sw.ElapsedMilliseconds);
        Console.WriteLine("Primes: " + _numbers.Count(i => i));
        var sum = 0;
        for (int i = 2; i < _numbers.Count(); i++)
            if (_numbers[i]) sum += i;
        Console.WriteLine("Sum of Primes: " + sum.ToString("n0"));

        Console.ReadLine();
    }

Dave Kreskowiak12-Sep-12 12:44

Dave Kreskowiak

12-Sep-12 12:44

Wow. With all this talk of Project Euler #10, I had to go dig up my answer to the problem from a couple of years ago. My implementation get the answer in 71 milliseconds, but I had mine built into a class and used tristates instead of booleans.

[EDIT]

Whoops. Might help if I wrap the stop watch around the code that generates the data and not include the code the sums up all the values. And it might help if I ran the Release version instead of the Debug.

New time: 17 milliseconds

A guide to posting questions on CodeProject[^]

Dave Kreskowiak

modified 12-Sep-12 18:52pm.

Clifford Nelson12-Sep-12 13:07

Clifford Nelson

12-Sep-12 13:07

Amazing, is it not. The questioner totally screwed up the algorithm, doing it the brut force way. Obviously took forever. Did not even realize was not doing the algorithm. Mine is not even optimal, made a slight change and got down to 24 ms.

Dave Kreskowiak12-Sep-12 18:25

Dave Kreskowiak

12-Sep-12 18:25

Yeah, some people shouldn't ask questions if they are going to deny every person giving them every correct answer.

A guide to posting questions on CodeProject[^]

Dave Kreskowiak

Thomas Daniels12-Sep-12 5:29

Thomas Daniels

12-Sep-12 5:29

This is an article about finding prime numbers using the Sieve of Eratosthenes:
Finding prime numbers[^]

It's in VB.NET, but you can download the source in C#.

Kenneth Haugland13-Sep-12 3:33

Kenneth Haugland

13-Sep-12 3:33

There are references to a pure C# implementation that sovles his problem completely there as well.

Substitution of Paths in HyperLinkField with File Names

PIEBALDconsult12-Sep-12 14:23

PIEBALDconsult

12-Sep-12 14:23

I don't think I've ever seen it done so inefficiently. OMG | :OMG:

0) You don't need to store the value; use the index.
1) You don't need to allocate space for even numbers.
2) You don't need to allocate a boolean (8-bit) just to store one bit worth of information.
3) You don't need to investigate the whole range; only investigate up to the square root (as others have already told you), then simply iterate the rest.

ASPnoob12-Sep-12 4:23

ASPnoob

12-Sep-12 4:23

Hi All, I am looking at a tutorial on using Gridview and the Hyperlinkfield, and I have question that I'd like to have an answer to. The tutorial I'm looking at is the article Practical Guide for Creating HyperLinkField in GridView in ASP.NET. In it, the author uses a gridview to display a student's information in four columns namely UserID, UserName, FilePath, and Photo. The FilePath column is what I'm interested in, when users click on links inside of it they can download students' profiles which are stored on the web server. The links are full paths to the profiles stored on the database. How do I modify the the code so that instead of seeing the full paths of files, all the users see are their names, and on top of that still enable users to download the profiles by clicking on the file names? Thanks in advance for your help.

Re: Substitution of Paths in HyperLinkField with File Names

Pete O'Hanlon12-Sep-12 4:55

Pete O'Hanlon

12-Sep-12 4:55

Shouldn't you be asking this on that article instead?

*pre-emptive celebratory nipple tassle jiggle* - Sean Ewington

"Mind bleach! Send me mind bleach!" - Nagy Vilmos

CodeStash - Online Snippet Management | My blog | MoXAML PowerToys | Mole 2010 - debugging made easier

Re: Substitution of Paths in HyperLinkField with File Names

ASPnoob12-Sep-12 9:59

ASPnoob

12-Sep-12 9:59

The article is quite old, I did not see any new activities lik questions being asked so I thought it wasn't active.

Retrieve name of Printer using SendMessage

toBeH_S11-Sep-12 22:10

toBeH_S

11-Sep-12 22:10

I want to get the name of the printer chosen in Acrobat PrintDialog using SendMessage Windows API.

This is sample code.

static string GetWindowText( hwnd_printDialog_in_Acrobat )
{
int comboBoxCount = 0;
int HWND_PRINTER_NAME = 1 ;

List<intptr> ChildPtrList = GetChildWindows(hwnd_printDialog_in_Acrobat);
for( i=0 ; i < ChildPtrList.Size(); i++) {
GetClassName( ChildPtrList[i], sClass, 100);
if (sClass.ToString() == "ComboBox") {
comboBoxCount++;
if (comboBoxCount == HWND_PRINTER_NAME ) {
hwnd = ChildPtrList[i];
break;
}
}
}
ChildPtrList.Clear();

int sSize ;
sSize = SendMessageW( hwnd, WM_GETTEXTLENGTH, IntPtr.Zero, IntPtr.Zero )+1;
StringBuilder sbTitle = new StringBuilder( sSize );
SendMessageW( hwn, WM_GETTEXT, (IntPtr)sSize, sbTitle);
return (sbTitle.ToString());
}

The return value of sSize is 4; The value of sbTitle.ToString() is "?-" etc.
The expected result what I want is "HP Officejet Pro .. ", for example.
What is wrong?

Thanks in advnace.

Rage12-Sep-12 6:40

Rage

12-Sep-12 6:40

toBeH_S wrote:
SendMessageW( hwn, WM_GETTEXT, (IntPtr)sSize, sbTitle);

You probably meant hwnd.

What is the following code doing:

StringBuilder title = new StringBuilder();

Int32 sSize = SendMessage((int)hWnd, WM_GETTEXTLENGTH, 0, 0).ToInt32();

// If the return is 0, there is no title. 
if (sSize > 0)
{
        sbTitle = new StringBuilder(sSize + 1);
        SendMessage(hwnd,( int)WM_GETTEXT, sbTitle.Capacity, sbTitle);

}
return sbTitle.ToString();

There could also be a Unicode problem.

~RaGE();

I think words like 'destiny' are a way of trying to find order where none exists. - Christian Graus
Do not feed the troll ! - Common proverb

toBeH_S12-Sep-12 8:33

toBeH_S

12-Sep-12 8:33

Rage wrote:

What is the following code doing:

StringBuilder title = new StringBuilder();
 
Int32 sSize = SendMessage((int)hWnd, WM_GETTEXTLENGTH, 0, 0).ToInt32();
 
// If the return is 0, there is no title. 
if (sSize > 0)
{
        sbTitle = new StringBuilder(sSize + 1);
        SendMessage(hwnd,( int)WM_GETTEXT, sbTitle.Capacity, sbTitle);
 
}
return sbTitle.ToString();

1. The above code retrieves the name of the printer chosen from the printer name combobox in printDialog.

hwnd : handle of the printer name combobox in PrintDialog of Acrobat.

1) Firstly, get the length of the printer name.

int sSize=SendMessage((int)hwnd, WM_GETTEXTLENGTH, 0,0),ToInt32();

2) Secondly, memory allocation for the name of the printer.

sbTitle = new StringBuilder( sSize + 1);

3) Finally, retrieve the name of the printer using SendMessage Windows API.

SendMessage(hwnd, (int)WM_GETTEXT, sbTitle.Capacity, sbTitle);

What I want is to retrieve the name of the printer chosen in acrobat printDialog from another application via SendMessage.

2.

Rage wrote:
There could also be a Unicode problem.

Maybe you right.
The original version is as follows:

if ( isWindowUnicode(hwnd)) {
        StringBuilder title = new StringBuilder();

         Int32 sSize = SendMessageW((int)hWnd, WM_GETTEXTLENGTH, 0, 0).ToInt32();

       // If the return is 0, there is no title.
       if (sSize > 0)
       {
                  sbTitle = new StringBuilder(sSize + 1);
                  SendMessageW(hwnd,( int)WM_GETTEXT, sbTitle.Capacity, sbTitle);

       }
      return sbTitle.ToString();
}

Rage12-Sep-12 21:25

Rage

12-Sep-12 21:25

toBeH_S wrote:
What is the following code doing:

With that statement I was actually trying to ask you to try the code I have put in my post: it is very similar to yours, with a few more tests to check the size (and hence check if the GETTEXTLENGTH is working) and some safer practices.

~RaGE();

I think words like 'destiny' are a way of trying to find order where none exists. - Christian Graus
Do not feed the troll ! - Common proverb