On Wednesday, 30 October 2013 at 06:04:36 UTC, Zeke wrote:
Hello, I'm on day 2 of learning D. I've learned C, C++, Java,
Python, Ruby in University, but I wanted to broaden my palette
by picking up D.
This project is a basic implementation of Project Euler problem
10. I build an array of primes, and for each new test number I
check if the test is divisible by any prime from 2 to
sqrt(test) (which cuts down on number of iterations). Trouble
is, I can't find a method that's in the libraries to calculate
the index of where sqrt(test) would exist or would be inserted
into a sorted array.
I tried casting the primes array to a SortedRange using
assumeSorted() but it didn't work for me. countUntil() returns
-1 if the value doesn't exist. and I didn't find anything in
the std.algorithm, std.array, or std.container.
Here's my current working implementation of is_prime and the
functions it uses:
pure nothrow @safe bool is_prime(in ulong[] primes, ulong num) {
// Need to find a more elegant way to find the index of
where a number's
// square root would be in a sorted array.
auto upper = insind(primes,
cast(ulong)sqrt(cast(double)num)) + 1;
// Check each prime in the array up to the square root of
our current test
// number to see if it is prime.
foreach(ulong prime; primes[0..upper]) {
if (num % prime == 0) {
return false;
}
}
return true;
}
Why do you want to find the exact prime first? Just check against
sqrt(num) in the loop.
auto upper = cast(ulong)sqrt(cast(double)num)) + 1;
foreach(ulong prime; primes) {
if (prime > upper) return true;
if (num % prime == 0) return false;
}
assert (false); // should be unreachable?
