eratosthenes.c

Denna kod är public domain. Om ni hittar fel eller vill ändra något i koden blir jag jätteglad om ni skickar dessa ändringar till jesper [at] fantasi [punkt] se.

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

/* Eratosthenes såll är en gammal grekisk algoritm som hittar alla primtal
 * upp till en given gräns.
 */

#define MAX 20000

int main()
{
   int count, i, k, prime, maxsize;
   bool mark;
   bool flags[MAX];

   printf("Ange övre gräns (max %d): ", MAX);
   (void)scanf("%d", &maxsize);
   printf("\n");
   if (maxsize > MAX)
   {
      printf("Jag vill inte räkna längre än till %d.\n", MAX);
      maxsize = MAX;
   }

   printf("I intervallet 3 .. %d finns följande primtal:\n", maxsize);
   printf("-----------------------------------------------\n");

   maxsize = (maxsize - 1) / 2;
   count = 0;
   mark = true;
   for (i = 0; i <= maxsize; i++)
      flags[i] = true;

   for (i = 1; i <= maxsize; i++)
   {
      if (flags[i])
      {
         prime = i + i + 1;
         printf("%8d", prime);
         count++;
         if (mark)
         {
            k = (i + i) * (i + 1);
            if ((k > maxsize) || (k < 0))
               mark = false;
            else
               while ((k <= maxsize) && (k > 0))
               {
                  flags[k] = false;
                  k = k + prime;
               }
         }
      }
   }

   printf("\n\nTotalt %d primtal.\n", count);
   return EXIT_SUCCESS;
}