On Thursday, 5 April 2012 at 17:22:38 UTC, Minas wrote:
Many of you should know the website "projecteuler.net", where
there are mathematical problems to solve with computers.
I am doing those in D, and after I finished one today, I
decided to compile it in C as well to compare the results.
The problem was:
"The number 3797 has an interesting property. Being prime
itself, it is possible to continuously remove digits from left
to right, and remain prime at each stage: 3797, 797, 97, and 7.
Similarly we can work from right to left: 3797, 379, 37, and 3.
Find the sum of the only eleven primes that are both
truncatable from left to right and right to left.
NOTE: 2, 3, 5, and 7 are not considered to be truncatable
primes."
My solution in D:
[source]
import std.stdio;
import std.math;
import std.conv;
void main()
{
int count, i = 10, sum;
while( count < 11 )
{
if( isPrime(i) && isPrimeRightToLeft(i) &&
isPrimeLeftToRight(i) )
{
//writeln(i);
++count;
sum += i;
}
++i;
}
writeln(sum);
}
/// returns true if n is a prime number
bool isPrime(ulong n)
{
n = abs(n);
// 0 and 1 aren't primes
if( n < 2 ) return false;
if( n % 2 == 0 && n != 2)
return false; // an even number can't be a prime (except 2)
// check only if it's odd
for(ulong i = 2; i <= cast (ulong)sqrt(cast(double)n+1); ++i)
if( n % i == 0 )
return false;
return true;
}
/**
* returns true if n is a prime* truncatable from right to left.
* Note: n must have been tested to be prime with a separate
function
*/
bool isPrimeRightToLeft(ulong n)
{
if( n < 10 )
return false;
n /= 10; // assuming that n has already been tested to be
prime, we can skip checking it
while( n > 0 )
{
if( !isPrime(n) )
return false;
n /= 10;
}
return true;
}
/**
* returns true if n is a prime* truncatable from left to right.
* Note: n must have been tested to be prime with a separate
function
*/
bool isPrimeLeftToRight(ulong n)
{
if( n < 10 )
return false;
ulong power = cast(ulong)pow(10, cast(ulong)log10(n));
ulong firstDigit = n / power;
n -= firstDigit * power;
while( n > 0 )
{
if( !isPrime(n) )
return false;
power = cast(ulong)pow(10, cast(ulong)log10(n));
firstDigit = n / power;
n -= firstDigit * power;
}
return true;
}
[/source]
In C:
[source]
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
typedef unsigned long ulong;
int isPrime(ulong n);
int isPrimeRightToLeft(ulong n);
int isPrimeLeftToRight(ulong n);
int main()
{
int count = 0, i = 10, sum = 0;
while( count < 11 )
{
if( isPrime(i) && isPrimeRightToLeft(i) &&
isPrimeLeftToRight(i) )
{
//writeln(i);
++count;
sum += i;
}
++i;
}
printf("%d\n", sum);
return 0;
}
/// returns true if n is a prime number
int isPrime(ulong n)
{
n = abs(n);
// 0 and 1 aren't primes
if( n < 2 ) return 0;
if( n % 2 == 0 && n != 2)
return 0; // an even number can't be a prime (except 2)
// check only if it's odd
for(ulong i = 2; i <= (ulong)sqrt((double)n+1); ++i)
if( n % i == 0 )
return 0;
return 1;
}
/**
* returns 1 if n is a prime* truncatable from right to left.
* Note: n must have been tested to be prime with a separate
function
*/
int isPrimeRightToLeft(ulong n)
{
if( n < 10 )
return 0;
n /= 10; // assuming that n has already been tested to be
prime, we can skip checking it
while( n > 0 )
{
if( !isPrime(n) )
return 0;
n /= 10;
}
return 1;
}
/**
* returns 1 if n is a prime* truncatable from left to right.
* Note: n must have been tested to be prime with a separate
function
*/
int isPrimeLeftToRight(ulong n)
{
if( n < 10 )
return 0;
ulong power = (ulong)pow(10, (ulong)log10(n));
ulong firstDigit = n / power;
n -= firstDigit * power;
while( n > 0 )
{
if( !isPrime(n) )
return 0;
power = (ulong)pow(10, (ulong)log10(n));
firstDigit = n / power;
n -= firstDigit * power;
}
return 1;
}
[/source]
And this is the time execution of the programs:
In D:
real 0m1.648s
user 0m1.644s
sys 0m0.000s
In C:
real 0m0.766s
user 0m0.760s
sys 0m0.000s
There's quite a big difference here. Is that normal or is there
something wrong? (Maybe a bug?)
* C source file was compiled as "gcc euler37.c -o euler37 -lm
-std=c99 -O5
D source file was compiled as "dmd euler37.d -O -release"
** In gcc as well in dmd sizeof(ulong) == 8
My guess would be still worse optimization capabilities of dmd.
Try with gdc and see.
