/*
Programmazione II - Esempio di codice
<![CDATA[
Example code: binary search demonstration. (20000809 prelz@mi.infn.it)
*/
#include <stdio.h>
#include <stdlib.h>
#define ARRAY_SIZE 100
#ifndef TRUE
#define TRUE 1
#endif
#ifndef FALSE
#define FALSE 0
#endif
int
main(int argc, char *argv[])
{
char in[800]; /* Generic input storage */
int primes[ARRAY_SIZE];
int req;
int i;
int upper_bound, lower_bound;
int current_guess;
int found = FALSE;
/* Let's build an array with the first 100 prime numbers */
for (i=0;i<ARRAY_SIZE;i++)
{
get_next_prime(primes,i);
}
printf ("Please enter an integer number --->");
fgets(in, sizeof(in), stdin);
req = atoi(in);
upper_bound = ARRAY_SIZE - 1;
lower_bound = 0;
current_guess = (upper_bound + lower_bound) / 2;
while (upper_bound >= lower_bound)
{
if (primes[current_guess] == req)
{
found = TRUE;
break;
}
else if (primes[current_guess] < req)
{
lower_bound = current_guess + 1;
}
else
{
upper_bound = current_guess - 1;
}
current_guess = (upper_bound + lower_bound) / 2;
}
if (found)
{
printf("I found the number %d to be one of the first %d prime numbers.\n",
req, ARRAY_SIZE);
}
else
{
printf("The number %d is NOT one of the first %d prime numbers.\n",
req, ARRAY_SIZE);
}
exit(0);
}
int
get_next_prime(int *primes, int count)
{
int i,j;
if (count == 0)
{
primes[0] = 1;
return(primes[0]);
}
for(i=primes[count-1]+1;;i++)
{
for (j=count-1;j>=0;j--)
{
if ( ((float)i/(float)primes[j]) == (float)(i/primes[j]) )
{
if (primes[j] > 1) break;
else
{
primes[count] = i;
return(primes[count]);
}
}
}
}
/* Should never reach here */
}
]]></plaintext></span>