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.

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.