Try any numbers, but these numbers make the program crash 2468,
8902
conjecture.c
#include <stdio.h>
#include "sieve.h"
#include <string.h>
int getPrimes (int a[], int low, int high, int num, int lowIndex,
int HighIndex);
int getNextIndex (int a[], int index, int s);
extern int holder[];
/**
* assigns two variables to store primes, one the
* smallest prime (low prime) and another stores the highest
* prime that is less than num (high prime)
*/
int
main ()
{
findPrimes ();
int infinite = 1;
while (infinite)
{
int num; // the even number that can be represented by two primes
if (scanf ("%d", &num) == EOF)
break;
if (num % 2 != 0 || num < 3 || num > 100000)
{
fprintf (stderr, "%d is an invalid number\n", num);
continue;
}
int high = 0; // the low prime
int low = 0; // the high prime
int highIndex = 0;
int lowIndex = 0;
low = holder[lowIndex]; // initially low prime is first element (2)
int i = 0;
for (; i < N - 1; i++) // find the high prime
{
if (holder != 0 && holder < num)
high = holder;
highIndex = i;
}
getPrimes (holder, low, high, num, lowIndex, highIndex);
}
return 0;
}
/**
* given both the low and high prime, this function
* will increase the low prime and decrease the
* high prime until low prime + high prime = num
*/
int
getPrimes (int a[], int low, int high, int num, int lowIndex, int highIndex)
{
if (lowIndex > N - 1 || highIndex < 0)
{
printf ("No primes found\n");
return 1;
}
else if (high + low == num)
{
printf ("%d %d\n", low, high);
return 0;
}
else if (high + low < num) // get the next biggest low prime
{
lowIndex = getNextIndex (holder, lowIndex, 0);
low = holder[lowIndex];
return getPrimes (holder, low, high, num, lowIndex, highIndex);
}
else if (high + low > num) // get the next smallest high prime
{
highIndex = getNextIndex (holder, highIndex, 1);
high = holder[highIndex];
return getPrimes (holder, low, high, num, lowIndex, highIndex);
}
return 1;
}
/**
* returns the index of the next prime
* if s = 0 then search to the right of current index in the array
* if s = 1 then search to the left of current index in the array
*/
int
getNextIndex (int a[], int index, int s)
{
if (s == 0)
{
int i = index + 1;
for (; i < N - 1; i++)
{
if (a != 0)
return i;
}
}
else
{
int i = index - 1;
for (; i >= 0; i--)
{
if (a != 0)
return i;
}
}
return 1;
}
===========
sieve.c
#include <math.h>
#include <stdio.h>
#include "sieve.h"
int findPrimes ();
int holder[N];
/**
* findPrimes() stores all the primes
* from 2 to N in an array.
*/
int
findPrimes ()
{
int i = 0;
int j = 2;
for (; i < N - 1; i++) // delete first two elements
{ // and shift all elements two places to the left
holder = j;
++j;
}
float fN = N;
float square = sqrt (fN);
int prime = 0;
int k = 0;
for (; k < N - 1; k++)
{ // loop finds next prime
if (holder[k] == 0)
continue;
prime = holder[k];
if (holder[k] > square) // no need if to continue
break; // if prime is > square of N
int p = k + 1;
for (; p < N - 1; p++)
{ // loop finds multiples of prime
if (holder[p] == 0) // then get next element
continue;
if (holder[p] % prime == 0)
{ // its a multiple
holder[p] = 0;
}
}
}
return 0;
}
===============
the header file
enum
{ N = 100000 };
extern int holder[];
int findPrimes ();
