in C++ write the progarm with the two functions The Sieve of Eratosthenes and Go
ID: 3802680 • Letter: I
Question
in C++ write the progarm with the two functions
The Sieve of Eratosthenes and Gold Bach's Conjecture Implement the Sieve of Eratosthenes and use it to find all prime numbers less than or equal to one million. Use the result to prove Gold Bach's Conjecture for all even integers between four and one million, inclusive. Implement a function with the following declaration; void sieve (int array [], int num); This function takes an integer array as its argument. The array should be initialized to the values 1 through 1000000. The function modifies the array so that only the prime numbers remain; all other values are zeroed out. This function must be written to accept an integer array of any size. You must should output for all primes numbers between 1 and 1000000. but when I test your function it may be on an array of a different size. Implement a function with the following declaration: void gold Bach (int array[], int num); This function takes the same argument as the previous function and displays each even integer between 4 and 1000000 with two prime numbers that add to it. The goal here is to provide an efficient implementation. This means no multiplication, division, or modulus when determining if a number is prime. It also means that the second function must find two primes efficiently. Output for your program: All prime numbers between 1 and 1000000 and all even numbers between 4 and 1000000 and the two prime numbers that sum up to it.Explanation / Answer
copyable code:
#include <bits/stdc++.h>
using namespace std;
void sieve(bool array[],int num)
{
for (int i=2; i*i<=num; i++)
{
// validates the array
if (array[i] == 1)
{
// Updating all multiples of i
for (int j=i*2; j<=num; j += i)
array[j] = 0;
}
}
int tmp[num],i=0,val_cnt=0;
// Print all prime numbers
for (int val=2; val<=num; val++)
{
if (array[val])
{
tmp[i]=val;
cout << tmp[i] << " ";
i++;
val_cnt++;
}
}
cout << " ***Goldbach's Conjecture***";
cout<< " Even numbers between 4 and given array size and sum's value are " ;
for(int i=0;i<val_cnt;i++)
{
for(int j=i+1;j<val_cnt;j++)
{
int tot;
tot = tmp[i]+tmp[j];
if((tot%2==0) && (tot <num))
cout<< tot << " ";
}
}
}
//calculates the tot od tmp numbers whose result is even
void goldbach(bool array[], int num)
{
sieve(array,num);
}
// main method
int main()
{
int num = 120;
bool array[num+1];
memset(array, 1, sizeof(array));
cout << " ***Sieve of Erastosthenes***" << endl;
cout << " The Prime numbers than or equal to " << num << endl;
goldbach(array,num);
return 0;
}
output:
***Sieve of Erastosthenes***
The Prime numbers than or equal to 120
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
***Goldbach's Conjecture***
Even numbers between 4 and given array size and sum's value are
8 10 14 16 20 22 26 32 34 40 44 46 50 56 62 64 70 74 76 82 86 92 100 104 106 110 112 116 12 16 18 22 24 28 34 36 42 46 48 52 58 64 66 72 76 78 84 88 94 102 106 108 112 114 118 18 20 24 26 30 36 38 44 48 50 54 60 66 68 74 78 80 86 90 96 104 108 110 114 116 24 28 30 34 40 42 48 52 54 58 64 70 72 78 82 84 90 94 100 108 112 114 118 30 32 36 42 44 50 54 56 60 66 72 74 80 84 86 92 96 102 110 114 116 36 40 46 48 54 58 60 64 70 76 78 84 88 90 96 100 106 114 118 42 48 50 56 60 62 66 72 78 80 86 90 92 98 102 108 116 52 54 60 64 66 70 76 82 84 90 94 96 102 106 112 60 66 70 72 76 82 88 90 96 100 102 108 112 118 68 72 74 78 84 90 92 98 102 104 110 114 78 80 84 90 96 98 104 108 110 116 84 88 94 100 102 108 112 114 90 96 102 104 110 114 116 100 106 108 114 118 112 114
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.