sieve of eratosthenes -sieve of eratosthenes segmentation fault

[catchmrbharath]

I am having a problem in implementing of sieve of eratosthenes..
please check the code and tell me the error

#include<iostream>
#include<cstdio>
using namespace std;
int main()
{
  int i,j;
  long array[100001];
  int count=0;
  for(i=1;i<100001;i++)
    {    
array[i]=i;

    }
  for(i=2;i<100001;i++)
    {
    if(array[i]!=0)
      {
	cout<<""<<array[i]<<endl;
	int j=0;
	j=i*i;
	while(j<100001)
	  {
	    array[j]=0;
	    j+=i;
	  }
      }
    }


}

[mvmalderen]

j=i*i;
while(j<100001)
{
    array[j]=0;
    j+=i;
}

This will cause an array overrun :)

Edit:: Sorry I replied to quickly :$

[catchmrbharath]

I didnt get you. what do you mean by array overrun??

[mvmalderen]

I didnt get you. what do you mean by array overrun??

This means that you try to access an element in the array, where you didn't declare memory for...

BTW, you're not using variable count anywhere in your code :)

[mvmalderen]

Change your code to this:

#include<iostream>
#include<cstdio>
using namespace std;
int main()
{
  int i,j;
  long array[100001];
  int count=0;
  
  for(i=1;i<100001[B]UL[/B];i++)
  {    
		array[i]=i;
  }
  
  for(i=2;i<100001[B]UL[/B];i++)
  {
    if(array[i]!=0)
    {
		cout<<""<<array[i]<<endl;
		int j=0;
		j=i*i;
		while(j<100001[B]UL[/B])
		  {
			array[j]=0;
			j+=i;
		  }
    }
  }
  
}

:)

[Sky Diploma]

Firsty, The Code for The Sieve is faulty.Actually its not a sieve at all.

But anyways, Lets come back to the Segmentation fault,
The reason for the segmentation fault is that your code j=i*i; is actually causing j to cross the bounds of an integer at a high value of somewhere around 46000. to be exact its at 46349.

However even if that is corrected, your sieve is still not proper.

replace

j=i*i;

to

j=i*2;//ie: i+i

By that we find the factor of the number .

Though the method will work out, it can be made a lot more efficient. But as you wanted the sieve of erathosthenes thats to it. :)

EDIT::BAD POST PLEASE DONT MIND READING!!

[catchmrbharath]

But i am checking for a condition j<100001 right?? So i am not accessing anything more than array[100000] .

[Sky Diploma]

Yes, But are you checking for the arrays lower bound?

I mean is 0<j?

[catchmrbharath]

If i use long for j instead of int will it work???

[Sky Diploma]

Hey, Checkout Tux's post to remove the Segmentation Fault,

Though, The fault is removed, There is still a problem technically in your code. read my previous post.

EDIT::BAD POST

[siddhant3s]

>If i use long for j instead of int will it work???
Yes

Edit: Why?
100001*100001=10000200001
So obviously a int cannot hold this number.

Adding UL won't solve the thing
Edit2: I realized that adding UL does solved the problem. I am don't think it is good. You should rather change the type of j to unsigned long

[catchmrbharath]

I didnt understand how by adding UL ,the segmentation fault is removed

[catchmrbharath]

The sieve was right. Using i*i is not a problem because all the elements like i*2,i*3 are eliminated initially if i>2 &i>3 ...and so on...

[catchmrbharath]

@Siddhanth

Adding UL solved the thing and making j long didnt solve it

[siddhant3s]

>>Adding UL solved the thing and making j long didnt solve it
Don't add UL, Make the j a unsigned long.
I am sensing adding UL is dangerous. But I have no reference right now. I will find and then post it.
j should be a unsigned long

[catchmrbharath]

Changing j to unsigned long did the trick.. Thanks ..

[Sky Diploma]

Oh Sorry, I guess you are right in multiplying i*i, I dint realise that before, And I also agree that i pushed your answer into a wrong direction i mean (mislead you).

Anyways, The unsigned specifier makes the number non-negative and thereby the arrays bounds are not crossed,

It is not only an unsigned long, but the code would have worked out even if it was an unsigned int i guess. And it does.

[mvmalderen]

>>Adding UL solved the thing and making j long didnt solve it
Don't add UL, Make the j a unsigned long.
I am sensing adding UL is dangerous. But I have no reference right now. I will find and then post it.
j should be a unsigned long

Yeh, I changed it while testing, but I forgot to change it in the OP's code :P

[mvmalderen]

An example of a program which implements the 'Eratosthenes Sieve':
http://www.daniweb.com/code/snippet1205.html :)

And yes, I know, sorry that the code is not fully formatted, that is because I wrote it before I discovered WaltP's excellent code formatting guide :)

And yes siddhant3s, you're probably right that it's better to just make the loop index an unsigned long variable, making it (the value 100001 or something) an unsigned long literal was maybe not the best idea :)
(but it will cause the integer variable each time to be implicitly converted to an unsigned long, so the high order bit will be interpreted in another way, and because the value still fits in that range (if you interpret the high order bit of the integer datatype in another way), it's probably why this nasty trick worked, but now I'm having a doubt whether it's a good practice to do so, personally I don't think so because it's just more error prone (and it wouldn't have worked with larger numbers)...

To the OP: Do what siddhant3s has said: define the variable as an unsigned long :)

[siddhant3s]

>And yes, I know, sorry that the code is not fully formatted, that is because I wrote it
>before I discovered
At least I don't expect you to format a code which is not yours. I mean it is just enough for you to post unformatted code provide it doesn't cause much harm to the eyes. For larger and complex program, formatting is essential.
>WaltP's excellent code formatting guide
I don't see a point in formatting your code "by hand" although it is a good practice. These days, source code pretty-fier are available which performs very impressive formatting. Astyle is my favorite. Just call the program with your filename as an argument and you are done. ( Using astyle become more easy on windows since you just have to drag and drop on the exe icon.)
>but it will cause the integer variable each time to be implicitly converted to an
>unsigned long
Yes. This is a clear point of not using that trick but I was wondering that if it will cause some portability issue. I am sure of it but cannot find some references.