Must be C++. Using Microsoft Visual Studio as the compiler. The Sieve of Eratost
ID: 646583 • Letter: M
Question
Must be C++. Using Microsoft Visual Studio as the compiler.
The Sieve of Eratosthenes is a method used to find prime numbers.
The algorithm is as follows:
a.) Create an array with all elements initialized to 1.
b.) Starting with array subscript 2, every time an array element is found whose value is 1, loop through the remainder of the array and set to 0 every element whose subscript is a multiple of the subscript with value 1.
c.) When this process is complete, the array elements that are still set to 1 indicate that the subscript is a prime number. Code the algorithm given above and provide a working program that prints the prime numbers less than 1000.
Be certain to make your program flexible enough so that you can easily change it to look for prime numbers of any size. In addition to having the program print the prime numbers less than 1000, at the end of the program run also print the number of prime numbers less than 1000. i.e. the quantity of numbers printed out by your program.
Explanation / Answer
#include <stdio.h>
#define SIZE 300
void printArray(int b[SIZE]);
int countHowManyPrimes(int b[SIZE]);
void isPrime(int b[SIZE]) ;
int main(void) {
int array[SIZE]={0};
isPrime(array);
printArray(array);
printf(" %d total prime numbers till %d. ", countHowManyPrimes(array),SIZE);
getch();
return 0;
}
//prints prime numbers
void printArray(int b[SIZE]){
int i;
for (i = 2; i < SIZE; i++)
{
if(b[i]==0)
printf("%d is a prime number. ",i);
}
}
//counts total prime numbers
int countHowManyPrimes(int b[SIZE]){
int i,count=0;
for (i = 2; i < SIZE; i++)
{
if(b[i]==0)
count++;
}
return count;
}
//finds prime numbers through iteration
void isPrime(int b[SIZE]){
int i,j,m;
for (i = 2; i < SIZE; i++)
{
j=i;
for (m = j+1; m < SIZE; m++)
{
if (m%j==0)
{
b[m]=1;
}
}
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.