Program in C Program in C The Sieve of Eratosthenes is a fast method to determin

Question

Program in C
Program in C



The Sieve of Eratosthenes is a fast method to determine all primes less than or equal to a given number N. The method proceeds as follows. Initially, we write down all the integers from 2 to N We start with the first prime, P-2. After finding each new prime P (initially, P 2), we cross out all multiples of P starting with 2 x P from the list of numbers; this can be easily done by crossing out every Pth entry starting from the number 2 x P (but only considering the numbers up to N) Then, P is incremented to the next non-crossed-out integer. Again, we cross out all multiples of P starting with 2 ×P and increment P to the next non-crossed-out number, we repeat these steps until P > VN. The numbers that have not been crossed out in the end represent all prime numbers smaller than or equal to N. Write a program for N = 100,000. At the end, the program should print out all primes up to N-100,000. You should use an integer array (of size 100,001 or so) to store the status (crossed out or not) of all integers. For example, the array may be declared as int sieve [100001] make sure you initialize all elements of the array properly to avoid problems. Your output should start with the following sequence (to help you check your code): 13 17 19 23 29 31 37 41 The output should end with sequence (for N-100,000): 99829 99833 99839 99859 99871 99877 99881 99901 99907 99923

Explanation / Answer

#include <stdio.h>

int main()
{
int i, count,j,inc=0;
long int Number=100000;
long int sieve[100001];
// printf(" Please Enter the Number");
// scanf("%d",&Number);

   printf("Prime Numbers from 1 to %d ",Number);
for(j=1; j<= Number; j++)
{
    count = 0;
    for (i = 2; i <= j/2; i++)
    {
      if(j%i == 0)
      {
   count++;
   break;
      }
    }
    if(count == 0 && j != 1 )
    {
        sieve[inc]=j;
      // printf(" %d ", j);
       inc++;
    }
}

printf(" ");
for(j=0; j<inc; j++){
     
       printf("%d ",sieve[j]);
}

return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.