A prime is an integer that can only divisible by 1 and itself. For example, 2,3,

Question

A prime is an integer that can only divisible by 1 and itself. For example, 2,3,5,7,11,13,17,... etc are primes. In 1742, Goldbach gave the famous conjecture Every even integer greater then 2 can be written us the sum of two primes. For example, 100 = 3 + 97, 1000 = 3 + 997,... This is still an open problem. No one can prove or can disprove Goldbach's conjecture yet. Write a program to test Goldbach's conjecture for n from 6 to 20,000,000. Use clock() function to measure your running time. Try to speed up your program as fast as possible without concerning memory space. Output should include the running time of your program and results from 900,000 to 900,100.

Explanation / Answer

#include <stdio.h>
#include <time.h>
#define MAX_NUM 20000001
// array will be initialized to 0 being global
int primes[MAX_NUM];

void gen_sieve_primes(void)
{
int p;
for (p=2; p<MAX_NUM; p++) // for all elements in array
{
   if(primes[p] == 0) // it is not multiple of any other prime
   primes[p] = 1; // mark it as prime

   // mark all multiples of prime selected above as non primes
   int c=2;
   int mul = p * c;
   for(; mul < MAX_NUM;)
   {
   primes[mul] = -1;
   c++;
   mul = p*c;
   }
}
}
int main()
{
clock_t t;
t = clock();
gen_sieve_primes();
int i;
for (i=6;i<20000000;i=i+2)
{
   int j=2,temp=0;
   for (j=2;j<i;j++)
   {
   if(primes[j]==1 && primes[i-j]==1)
   {
       if (i>=900000 && i<=900100)
           printf("%d=%d+%d ",i,j,i-j);
       temp=1;
       break;
   }
   }
   if (temp!=1)
   {
   printf("%d doesn't satisfy Goldbach's conjecture ",i);
   break;
   }
}
t = clock() - t;
double time_taken = ((double)t)/CLOCKS_PER_SEC; // in seconds
printf("code took %f seconds to execute ", time_taken);
return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

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