Please I need help in writing the program below.Thanks The Greek mathematician E
ID: 3608834 • Letter: P
Question
Please I need help in writing the program below.ThanksThe Greek mathematician Eratosthenes developed an algorithm knownas the Sieve of Eratosthenes for finding all prime numbers lessthan or equal to a given number n- that is, all primes in the range2 through n. Consider a list of numbers from 2 through n. Two usthe first prime number, but the multiple of 2 (4, 6, 8…) arenot, and so they are crossed out in the list. The first numberafter 2 that was not crossed out is 3, the next prime. We thencross out from the list all higher multiples of 3 (6, 9, 12…). The next number not crossed out is 5, the next prime, andso we cross out all higher multiples of 5 (10, 15, 20...). Werepeat this procedure until we reach the first number in the listthat has not been crossed out and whose square is greater than n.all the numbers that remain in the list are the prime number from 2through n. Write a C++ program that uses this sieve method and anarray to find all prime numbers from 2 through n. Execute theprogram for n= 550 and for n= 5500. Please I need help in writing the program below.Thanks
The Greek mathematician Eratosthenes developed an algorithm knownas the Sieve of Eratosthenes for finding all prime numbers lessthan or equal to a given number n- that is, all primes in the range2 through n. Consider a list of numbers from 2 through n. Two usthe first prime number, but the multiple of 2 (4, 6, 8…) arenot, and so they are crossed out in the list. The first numberafter 2 that was not crossed out is 3, the next prime. We thencross out from the list all higher multiples of 3 (6, 9, 12…). The next number not crossed out is 5, the next prime, andso we cross out all higher multiples of 5 (10, 15, 20...). Werepeat this procedure until we reach the first number in the listthat has not been crossed out and whose square is greater than n.all the numbers that remain in the list are the prime number from 2through n. Write a C++ program that uses this sieve method and anarray to find all prime numbers from 2 through n. Execute theprogram for n= 550 and for n= 5500.
Explanation / Answer
#include<iostream>
using namespace std;
int main()
{
int arr[10000];
int n;
int i,j;
for(i=1;i<sizeof(arr)/sizeof(int);i++)
arr[i]=i;
for(i=2;i<sizeof(arr)/sizeof(int);i++)
{
if(arr[i]!=-1)
{
for(j=2*arr[i];j<sizeof(arr)/sizeof(int);j=j+arr[i])
{
arr[j]=-1; // Cross the number
}
}
}
cout<<"Enter n:";
cin>>n;
cout<<"Prime number upto " <<n<<"are "<<endl;
for(i=2;i<n;i++)
if(arr[i]!=-1)
cout<<arr[i]<<" ";
system("pause");
}
/*
Sample output
Enter n:550
Prime number upto 550 are
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
389
397
401
409
419
421
431
433
439
443
449
457
461
463
467
479
487
491
499
503
509
521
523
541
547
Press any key to continue . . .
*/