nly divis- ible only by itself and 1. The Sieve of Eratosthenes is an algorithm

Question

nly divis- ible only by itself and 1. The Sieve of Eratosthenes is an algorithm for finding prime numbers, It a) Create an array with all elements initialized to 1 (true). Array elements with prime in (The Sieve of Eratosthenes) A prime integer is an integer greater than 1 that's eve 10.16 operates as follows: dices will remain as 1. All other array elements will eventually be set to zero. b) Set the first two elements to zero, since 0 and 1 are not prime. Starting with array index 2, every time an array element is found whose value is 1, loop through the remainder of the array and set to zero every element whose index is a multiple of the index for the element with value 1. For array index 2, all elements beyond 2 in the array that are mul- tiples of 2 will be set to zero (indices 4, 6, 8, 10, etc.); for array index 3, all elements beyond 3 in the array that are multiples of 3 will be set to zero (indices 6, 9, 12, 15, etc.); and so on. When this process is complete, the array elements that are still set to 1 indicate that the index is a prime number. These indices can then be printed. Write a script that uses an array of 1000 ele- ments to determine and print the prime numbers between 1 and 999. Ignore element 0 of the array

Explanation / Answer

#include<stdio.h>

void SieveOfEratosthenes(int n)
{

int prime[n+1];
int i=0;
int p=0;
  
for(i=0;i<n+1;i++)
prime[i]=1;

for ( p=2; p*p<=n; p++)
{
  
if (prime[p] == 1)
{
  
for ( i=p*2; i<=n; i += p)
prime[i] = 0;
}
}

  
for ( p=2; p<=n; p++)
if (prime[p])
printf("%d ",p);
}

int main()
{
int n = 1000;
printf("Prime Numbers between 1 and 999 are ");   
SieveOfEratosthenes(n);
return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse N
• Subjects

---

---

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