Write a program that will be a prime number generator using the Sieve of Eratost

Question

Write a program that will be a prime number generator using the Sieve of Eratosthenes. This program involves manipulations on a rather large array. In your program all array operations will be done using pointers. Square brackets ('[' and ']') should not appear anywhere in the program.
The program will first ask the user for an upper limit on the primes to compute, will compute the primes and will then display them in an orderly manner. When run the program may display:

find primes up to: 386
2 3 5 7 11 13
17 19 23 29 31 37
41 43 47 53 59 61
67 71 73 79 83 89
97 101 103 107 109 113
127 131 137 139 149 151
157 163 167 173 179 181
191 193 197 199 211 223
227 229 233 239 241 251
257 263 269 271 277 281
283 293 307 311 313 317
331 337 347 349 353 359
367 373 379 383
The "sieve" is an array hold[] with positions having indices running up to the maximum value, MAX, to be considered. For example, to compute all prime numbers up to 1000 you would need an array of length 1001 (index values 0 through 1000). Each position will represent the integer which is its index. Since the lowest prime is 2 we will only use positions 2 through MAX. A number i will be marked prime by putting a 1 in the corresponding array position hold[i] or marked composite by placing a 0.
Initially all numbers will be marked (with 1) as prime. As numbers are discovered to be composite their marks will be changed to 0. Even numbers greater than 2 will first be marked composite by a loop running from 4 up to MAX in steps of 2. Multiples of 3 (except 3) will be marked composite by a loop beginning at 6 and running up to MAX in steps of 3. Multiples of 4 (or any number already found to be composite) need not be computed since they were marked as multiples of 2 (or some factor of the current number). Continuing this way all composite numbers will eventually be marked 0 and primes and be found by reading through hold[] and reporting only values of i where hold[i] is 1.
Notice that you need only mark multiples of i for values of i less than or equal to the square root of i. (#include <math.h>, (int)sqrt(i).) On a Unix system you now must add the "-lm" switch on the command line. This will cause your program to be linked with the math library where sqrt() lives


The program must have a hold[]that should be an array of char. Remember that char is an integer type so you can store values 0 and 1 as char. Your program will ask the user for an upper limit on the primes to compute and the answer will determine how large hold[] must be. Thus the array will be allocated with malloc() only after this size is know.
Besides main() your program should have (at least) a function ,void runsieve(char *array, int max),which makes repeated passes through the array marking composite numbers, and a function, also void showprimes(char *array, int max)and which reads through the array displaying the primes. showprimes() will display the primes in 6 columns with each value right justified in a field of 10 characters (format descriptor "%10d").
You may use scanf() for user input. You must check that the MAX value chosen by the user is at least 2. The program will continue to nag the user for input as long as he or she provides values less than 2.

Explanation / Answer

please rate - thanks

#include <stdio.h>
#include <conio.h>
#include <math.h>
#include <stdlib.h>   
int main()
{
int i,j,max;
printf("what number do you want to test to? ");
scanf("%d",&max);
int *hold=malloc(sizeof(int)*max);
for(i=0;i<max;i++)
      *(hold+i)=1;
for(i=2;i<=max;i++)
     if(*(hold+i)==1)
        for(j=i;j<max;j+=i)
             if(*(hold+j)==1&&j!=i)
                 *(hold+j)=0;   
printf("The prime numbers between 2 and %d are: ",max);
   j=0;
   for(i=2;i<max;i++)
      {if(*(hold+i)==1)
         { printf("%d ",i);
          j++;
        if(j%6==0)
              printf(" ");
        }
    }
printf(" ");

getch();
return 0;

}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

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