speeding up + ctfe question

[sclytrack]

On 05/26/2012 03:49 PM, maarten van damme wrote:
> I finally made the primerange I wanted to make. I think I'm using a
> rather dumb algorithm. The idea is to store the prime we're at in
> curPrime and the amount of preceding primes in countPrime. Then
> opindex is able to calculate how many primes following or preceding
> curPrime we have to find to get the asked value.
> I'm not english so some names can be poorly chosen. Code is at
> http://dl.dropbox.com/u/15024434/d/primeRange.d
>
> The problem is that it's pretty slow. I wanted to find the first prime
> number with 10 digits and it literally takes forever (but manages it
> though). Is there an easy way to speed up or is this the ceiling?
> (better algorithms, stupidity's I've left,...)
>
> I also have an array of primes I use to "quicktest" to see if
> something is a prime. You can change it's size using setQuicktestSize
> at runtime. I want to make it large at compile time though. as I'm new
> to ctfe I have no idea as to how one can do this.



See below for a rather dumb algorithm. The idea is to list
a list of prime numbers. The problem is that it is pretty
slow and you get a ...

//src/main.d(57): Error: template instance main.isDivisable!(499,498) 
recursive expansion

error when the number is too large. I'm not English so
the names ARE poorly chosen.


//writeln(primeList!(200)); //<---don't pick over 200 or it goes nuts
//writeln(decompose!(49,2));


template primeList(int index)
{
   static if (index > 1)
   {
     static if (isPrime!(index))
     {
       enum int [] primeList =  primeList!(index-1) ~ [index];
     } else
     {
       enum int [] primeList = primeList!(index-1);
     }
   }
   else
   {
     enum int [] primeList = [];
   }
}

template isDivisable( int number, int divisor)
{
   enum bool isDivisable = (number % divisor) == 0;
}
//	10 ---> [2,5]	

template decompose(int number, int d = 2)
{
   static if (d < number)
   {
     static if (isDivisable!(number, d))
     {
       enum int [] decompose = [d] ~ decompose!(number/d, d);
     }
     else
     {
       enum int [] decompose = decompose!(number, d+1);
     }
   } else
   {
     enum int [] decompose = [number];
   }
}

template isPrimeDecompose(int number, int d = 2)
{
   static if (d < number)
   {
     static if (isDivisable!(number, d))
     {
       enum bool isPrimeDecompose = false;
     } else
     {
       enum bool isPrimeDecompose = isPrimeDecompose!(number, d+1);
     }
   } else
   {
     enum bool isPrimeDecompose = true;
   }
}

template isPrime(int number)
{
   static if (number > 1)
    enum bool isPrime = isPrimeDecompose!(number, 2);
   else
    enum bool isPrime = false;
}