תודה לשלומי

הייתי צריך לנקות קצת את הראש היום בגלל באג שאני עובד עליו, ואז וראיתי הודעה על פרוייקט אויילר ב פלאנט.

מי שלא מכיר את פרוייקט אויילר , זה אחד המקומות היותר טובים שאני מכיר לנסות דברים תוך כדי לימוד.

ההצעה שלי לפתרון השאלה איך לעשות אופטימיזציה לחישוב מספר ראשוני היא שימוש ב composition (אבל זה בא על חשבון הקצעה) :

 
#include <stdio.h>
#include <time .h>
#include <string.h>

#define mMO_NUM_LIMIT (150000000)

static char mo_tabOfPrimes[mMO_NUM_LIMIT];

void mark_numbers_as_primes()
{
   int primeIndex;
   int compositionIndex;
   int maxNumberOfElemenentsInTab;
   memset(mo_tabOfPrimes,0,sizeof(mo_tabOfPrimes));
   maxNumberOfElemenentsInTab = sizeof(mo_tabOfPrimes)/sizeof(mo_tabOfPrimes[0]);

   for (primeIndex = 2 ;primeIndex < maxNumberOfElemenentsInTab;primeIndex ++ )
   {
     if (0 != mo_tabOfPrimes[primeIndex])
     {
       continue; //any number previously markes as a composition can no be prime
     }
     //any next value will be a composition of that code
     for (compositionIndex = primeIndex + primeIndex; compositionIndex < maxNumberOfElemenentsInTab;compositionIndex = compositionIndex + primeIndex)
     {
       mo_tabOfPrimes[compositionIndex] = 1;
     }
   }
}

int is_prime(const long indexToCheck)
{
  int check ;
  if (indexToCheck > mMO_NUM_LIMIT)
  {
    return 0;
  }
  return   (0 ==  mo_tabOfPrimes[indexToCheck]);
}

void printFirstNPrimes(int countToPrint)
{
  long i;
  int numberOfPrimesPrintedSoFar = 0;

  for (i = 0 ;
      ( i < mMO_NUM_LIMIT) &&( numberOfPrimesPrintedSoFar < countToPrint);
      i++)
  {
    if (1 == is_prime(i))
    {
       numberOfPrimesPrintedSoFar ++;
       printf("%d/%d %d is a prime number\n",numberOfPrimesPrintedSoFar,countToPrint,i);
    }
  }
}
int main()
{
   clock_t start;
   clock_t end; 
   double time_spent;

   start = clock();
   mark_numbers_as_primes();
   end = clock();
   time_spent = (end - start) / CLOCKS_PER_SEC;
   printf("spent %lf seconds when filling %lld prime numbers\n",time_spent,mMO_NUM_LIMIT);
   printFirstNPrimes(100);
   return 0;
}