#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int isPrime ( unsigned int n )
{
   unsigned int d, s;

   if ((n == 0) || (n == 1)) return 0;
   s = (unsigned int)sqrt(n);
   for (d = 2; d <= s; ++d) {
      if (n % d == 0) return 0;
   }
   return 1;
}

int main ()
{
   unsigned int s1, s3, n, cos;
   int prevs;

   /* Part 1 */
   s1 = s3 = 0;
   n = 1;
   while (s1 <= s3) {
      n += 2;
      if (isPrime(n)) {
         if (n % 4 == 1) ++s1; else ++s3;
      }
   }
   printf("*** Part 1: n = %u, s1 = %u, s3 = %u\n", n, s1, s3);

   /* Part 2 */
   prevs = 1; cos = 1;
   while (n < 1000000) {
      n += 2;
      if (isPrime(n)) {
         if (n % 4 == 1) ++s1; else ++s3;
         if ((prevs > 0) && (s1 < s3)) {
            ++cos; prevs = -1;
         } else if ((prevs < 0) && (s1 > s3)) {
            ++cos; prevs = 1;
         }
      }
   }
   printf("*** Part 2: Number of sign changes = %u\n", cos);

   exit(0);
}