Help on program

[k1ckthem1dget]

Can someone please help me with this program.

How would i go about writing a program which determines the prime numbers from 2 to 1000 in increasing order using the “sieve method of Eratosthenes”. AND Display the values determined to be prime for the user at the display device

[sicarie]

Can someone please help me with this program.

How would i go about writing a program which determines the prime numbers from 2 to 1000 in increasing order using the “sieve method of Eratosthenes”. AND Display the values determined to be prime for the user at the display device

Sure we can help - what do you have so far? Please post all your code and any compiler error messages.

[k1ckthem1dget]

I dont have much yet, i need help starting. Then i will see what happens, and post back with questions.
Thanks

[sicarie]

I dont have much yet, i need help starting. Then i will see what happens, and post back with questions.
Thanks

Well, to start it - can you tell me how you would do this, in a few sentences?

[DeMan]

The “sieve method of Eratosthenes” (as far as I know), is the idea that you start with a list of numbers, then remove all the multiples of the first number then the second (remaining) number etc so we would start with:
2,3,4,5,6,7,8,9 ,10,11,12,13,14 ,15,......,1000
and we first remove multiples of 2 (except itself) leaving:
2, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, ......999
Then we look at the next number (3) and remove all multiples of him:
2, 3, 5, 7, 11, 13, 17, 19, 23, 25, 29, .......997
Next we go for 5
2, 3, 5, 7, 11, 13, 17, 19, 23, 29,............ 997
etc.

Begin by setting up a list structure (you could use an array if you are unfamiliar with other structures, but personally I don't like this idea, because it means you would still iterate over 1000 elements (999 actually) to print only the primes leftover by going through the set several times already).

then (in a javanese dialect of pseudocode):

counter=0;
while myList has more elements
{
  currentElement=myList.elementAt(counter)
  counter++;
  counter2=counter
  while(counter2<myList.size())
  {
    if ((myList.elementAt(counter2) mod currentElement)==0)
    {
      myList.removeElement(counter2);
    }
    else
    {
      counter2++
    }
  }
}

then print out the list.
I'm not certain the logic above is correct, in particular counter2 (When you remove an element you don't need to increment it <convince yourself of this, draw a picture of what's happening if need be>).

Another way to approach program (which I would still argue uses the idea of the sieve of Eratosthenes (though your teacher/lecturer may not agree)) would use 2 lists:
The first one starts with all the numbers from 2..1000, the second starts empty.
We can then iterate through the elements in the first list, only adding it to the second list if it cannot be divided by any of the elements in the second list. (I initially though this was more efficient, but have changed my mind (well implemented it would have a similar efficiency to the code above)).

thus the logic would be more like:

for(int i=2; i<firstList.size(); i++)
{
  boolean prime=true;  //some will say this is bad logic (and their kinda right)
  for(int j=0;j<secondList.size(); j++)
  {
    if(firstList.elementAt(i) mod secondList.elementAt(j) == 0)
    {
      prime=false;
      break;  //out of the loop
    }
  }
  if(prime)
  {
    secondList.add(firstList.elementAt(i));
  }
}

I leave it to you to
a) make sure this is indeed the sieve of E
b) follow the logic to ensure it is correct
c) turn it into c (or whichever language you are using)

[shamik]

the above one seems to be quite difficult to understand
here is a very simple logic.

define an integer flag to keep track and initalize it.
int flag = 1;

now start a loop from starting no. i.e 2 till half of the ending no. i.e 500 (half of 1000) because no number greater than 500 would be able to devide 1000 exactly.

like this :

for(i=2;i<=500; i++)

then start another loop inside this starting from 2 till i .....like this :

for(j=2;j<=i;j+ +)

then devide i by j.... if ( i%j == 0)

then increment flag by 1.........flag+ +

close the if statement...... .....like this:

if ( i%j == 0)
{
flag++;
}

then close the for loop for j

now here if the value of flag>2 then its not a prime no.
so if the value of flag=2 then print the value because it is prime.

again make flag =0;

now close the for loop of i

you are done.

thanks and regards
shamik

[shamik]

the whole program is like this :

int flag = 1;

for ( i=2;i<1000;i++)
{
for( j=2;j<=i;i++)
{
if(i%j==0)
{
flag++;
}
}
if(flag<=2)
{
cout<<i<<endl;
}
flag = 0;
}

finish

The above post might have some mistakes coz its written to make u understand the logic. note that this is a just a logic of the code and not the entire program. it might vary depending on ur requirements.


thanks and regards.
shamik

[willakawill]

the whole program is like this :

int flag = 1;

for ( i=2;i<1000;i++)
{
for( j=2;j<=i;i++)
{
if(i% j==0)
{
flag++;
}
}
if(flag<=2)
{
cout<<i<<endl;
}
flag = 0;
}

finish

The above post might have some mistakes coz its written to make u understand the logic. note that this is a just a logic of the code and not the entire program. it might vary depending on ur requirements.


thanks and regards.
shamik

bool prime = true;
cout<<2<<endl;

for ( i = 3; i < 1001; i++ )
{
    for( j = 2; j < i; j++ )
    {
        if( i % j == 0 )
        {
            prime = false;
        }
    }
    if(prime)
    {
        cout<<i<<endl;
    }
    prime = true;
}

slightly modified to include # 1000 and fix some typos :)

[willakawill]

this is a little more 'cut & paste' for you and covers #2 in the algorithm in a sneaky way for you to discover :)

                bool prime = true;

	for (int i = 2; i < 1001; i++ )
	{
		for(int j = 2; j < i; j++ )
		{
			if( i % j == 0 )
			{
				prime = false;
			}
		}
		if(prime)
		{
			cout<<i<<endl;
		}
		prime = true;
	}

[k1ckthem1dget]

Thanks alot, i will post back in a few days with my code if i have any problems. Thanks again.