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;
}
