Error Sieve of Eratosthenes

[ram619]

I m trying to print the prime numbers using Sieve of Eratosthenes But, my output is 0 for all. please tell me where i m wrong.

Thanks for help

#include<stdio.h>
#include<conio.h>

int main()
{
    int arr[100],i,j=1,val=0,mod,num=0,k,l;
    
    for(i=0;i<100;i++)
    {
      arr[i]=j;
      j++;
    //  printf("\n %d",arr[i]);
    }
     
     for(k=1;k<100;k++) // checking number and replacing appropriate with 0
     {
        val=arr[k];
        
        if(val>0)
         {
           for(i=2;i<100;i++)
           {
           //  printf("\n %d",i);
             
             mod=arr[i]%val;
             
               if(mod==0)
               {
                 arr[i]=0;
               }
                else
                {
                    
                  continue;
                }
       
            }
         }
         else
         {
             continue;
         }
      }
      
      for(num=0;num<100;num++) // taking output
      {
        if(arr[num]>0)
        {
          printf("\n %d",arr[num]);
        }
        else
        {
            continue;
        }
      }
      
      getch();
}

[ram619]

Ok now i have corrected that above written code, the only problem now is that, its not printing just 7 and 5, rest all are in output

#include<stdio.h>
#include<conio.h>

int main()
{
    int arr[100],i,j=1,left,val;
    
    for(i=0;i<100;i++)
    {
      arr[i]=j;
      j++;
    }
    
    for(j=2;j<=7;j++)
    {      
        for(i=2;i<100;i++)
        {
          left=arr[i]%j;
    //      printf("\n %d",left);
          if(left==0)
          {
            arr[i]=0;
          }
          else
          {
            continue;
          }
        }
    }
    for(i=0;i<100;i++)
    {
     printf("\n %d",arr[i]);
    }
 
 getch();   
}

[gerard4143]

I just ran your code and your missing 3, 5, 7.

I think this works...Never checked it with valid prime numbers.

#include<stdio.h>

#define ARR_SIZE 100

int main()
{
    int arr[ARR_SIZE], i, j = 1, left;
    
    for(i = 0;i < ARR_SIZE; ++i)
    {
      arr[i] = j++;
    }
    
    for(j = 2; j <= ARR_SIZE; ++j)
    {      
        for(i = j; i < ARR_SIZE; ++i)
        {
          left = arr[i] % j;
		
          if(left == 0)
          {
            arr[i] = 0;
          }
          else
          {
            continue;
          }
        }
    }
    for(i = 0; i < ARR_SIZE; i++)
    {
		printf("\n %d",arr[i]);
    }
	return 0;  
}

[rxlim]

This particular algorithm depends on eliminating every multiple of each prime number (since that will not be a prime number), not the prime number them selves. When i = 2 arr will be 3, and during the second time in the outer loop when j = 3 you will check if arr % 3 == 0 which it is and you will eliminate a prime number. This will happen for every prime number j. If j == 5 you know that you already have eliminated all non prime numbers < 5, therefore you do not need to set i = 2 every time. Instead you should set i = j to avoid this problem, then arr will be j+1.

However, the point of Sieve of Eratosthenes, I think, is that you can get all prime numbers by calculation of all non prime numbers. A better way of implementing this would be to actually do this calculation, the calculation of all prime multiples, and only set them to zero. A very quick test showed that this method could be atleast 8 times faster than your current implementation. The basic steps to this algorithm can be found on wikipedia:

1. Create a list of numbers
2. Start with prime number 2 and eliminate all multiples of 2
3. Get the next non eliminated number (after 2) and eliminate all its multiples
(The next non eliminated number will be the next prime number)

And some home made psuedo code for your case could look something like this:

LastPrime <- 2
WHILE LastPrime*2 < 100 DO
  i <- 2
  WHILE i*LastPrime <= 100 DO
    NUM[i*LastPrime - 1] = 0
    i <- i + 1
  WHILE NUM[LastPrime] == 0 DO
    LastPrime <- LastPrime + 1

Where NUM is your list of numbers. I'm not really sure about the limits.. but something like that..

[ram619]

Thanks .............gerard4143 & rxlim