A prime integer is any integer greater than 1 that can be divided evenly only by
ID: 3687349 • Letter: A
Question
A prime integer is any integer greater than 1 that can be divided evenly only by itself and 1. The Sieve of Eratosthenes is a method of finding prime numbers. It works as follows:
a) Create an array with all elements initialized to 1 (true). Array elements with prime subscripts will remain 1. All other array elements will eventually be set to zero.
b) Starting with array subscript 2 (subscript 1 is not prime), 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 subscript is a multiple of the subscript for the element with value 1. For array subscript 2, all elements beyond 2 in the array that are multiples of 2 will be set to zero (subscripts 4, 6, 8, 10, and so on.). For array subscript 3, all elements beyond 3 in the array that are multiples of 3 will be set to zero (subscripts 6, 9, 12, 15, and so on.).
When this process is complete, the array elements that are still set to 1 indicate that the subscript is a prime number. Write a program that uses an array of 1,000 elements to determine and print the prime numbers between 1 and 999. Ignore element 0 of the array.
Use C language only
Explanation / Answer
To find all the prime numbers less than or equal to a given integer n by Eratosthenes' method:
1. Create a list of consecutive integers from 2 to n: (2, 3, 4, ..., n).
2. Initially, let p equal 2, the first prime number.
3. Starting from p, count up in increments of p and mark each of these numbers greater than p itself in the list.
These numbers will be 2p, 3p, 4p, etc.; note that some of them may have already been marked.
4. Find the first number greater than p in the list that is not marked.
If there was no such number, stop. Otherwise, let p now equal this number (which is the next prime), and repeat from step 3.
*/
#include<stdio.h>
void Eratosthenes(int n)
{
int boolean[n-1]; //boolean array holds 0 if the numbers is not prime
int list[n-1]; //store the numbers till given range from 2 onwards
int ctr,outctr,inctr,primeassm;
for(ctr=0;ctr<n-1;ctr++)
{ list[ctr]=ctr+2;//start storing numbers from 2 onwars
boolean[ctr]=1;//assume all to be prime
}
for(outctr=0;outctr<n/2+1;outctr++)
{
if(boolean[outctr]==1)
{
primeassm=list[outctr];//perform primality check for indivusal numbers
for(inctr=outctr+1;inctr<n-1;inctr++)
if(list[inctr]%primeassm==0)//if divisible set boolean to 0
boolean[inctr]=0;
}
}
printf(" The prime numbers till the given range are ");
for(ctr=0;ctr<n-1;ctr++)
if(boolean[ctr]==1)//display the list of prime numbers
printf("%d ",list[ctr]);
}
int main()
{
int num;
printf("ENTER THE RANGE WITHIN WHICH YOU WANT TO SEE THE PRIME NUMBERS ");
scanf("%d",&num);
Eratosthenes(num);
getch();
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.