(The Sieve of Eratosthenes) Create an array with all elements initialized to 1 (
ID: 655341 • Letter: #
Question
(The Sieve of Eratosthenes)
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.
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 greater than 1 that are still set to 1 indicate that the subscript is a prime number. Write a program (in MATLAB) that uses an array of 1000 elements to determine and print the prime numbers between 1 and 999. Ignore element 0 of the array.
Explanation / Answer
#include <stdio.h>
#define SIZE 1000
int main()
{
int nums[ SIZE ];
int i;
int a;
int primeCount = 0;
for ( i = 0; i < SIZE; i++ ) {
nums[ i ] = 1;
}
for ( i = 1; i < SIZE; i++ ) {
if ( nums[ i ] == 1 && i != 1 ) {
for ( a = i; a <= SIZE; a++ ) {
if ( a % i == 0 && a != i ) {
nums[ a ] = 0;
}
}
}
}
for ( i = 2; i < SIZE; i++ ) {
if ( nums[ i ] == 1 ) {
printf( "%3d is a prime number. ", i );
++primeCount;
}
}
printf( "A total of %d prime numbers were found. ", primeCount );
return 0;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.