By an almost unbelievable margin of being 300 million times faster: oiskuu's implementation from Anonymonk's implementation:

C:\test\C>gcm 3221225472
anonyM: gcm for s=3221225472 & r=1 to 1610612736 took:13.076620219
oiskuu: gcm for s=3221225472 & r=1 to 1610612736 took: 0.000000041
[download]

(And yes. I've verified the results. Otherwise I would have posted this hours ago.)

It all comes down to the extreme optimisability of the tail-recursive Euclidean gcd algorithm, which converges very, very fast.

The benchmark code (uncomment the comments for verification ):

#include <stdio.h>
#include <stdlib.h>
#include "mytypes.h"

U64 gcd( U64 a, U64 b ) {
    return !b ? a : gcd( b, a % b );
}

U64 lcm( U64 a, U64 b ) {
    return a * b / gcd( a, b );
}

U64 gcm( U64 max, U64 n ) {
    U64 c, lcm;

    for( c = 1; ( ~n & 1 ) && ( c < 4096 ); c <<= 1 ) n >>= 1;
    lcm = n * 4096;
    return ( max / lcm ) * lcm;
}

#define GB ( 1024ull * 1024ull * 1024ull )
#define PAGE 4096

void main( int argc, char **argv ) {
    U64 s = argc > 1 ? _atoi64( argv[ 1 ] ) : 2*GB;
    U64 r, start, end, gsm;
//    U64 *res = malloc( sizeof(U64) * (s>>1) );

    start = __rdtsc();
    for( r = 1; r < ( s >> 1 ); ++r ) {
//        res[ r ] =
        gsm = gcm( s, r );
    }
    end = __rdtsc();
    printf( "anonyM: gcm for s=%I64u & r=1 to %I64u took:%.9f\n", s, s
+>>1, (double)( end - start ) / 2394046359.0 );

    start = __rdtsc();
    for( r = 1; r < ( s >> 1 ); ++r ) {
//        if( res[ r ] !=
            ( gsm = s - ( s % lcm( r, 4096 ) ) )
//        ) printf( "%I64u != %I64u\n", gsm, res[ r ] )
        ;
    }
    end = __rdtsc();
    printf( "oiskuu: gcm for s=%I64u & r=1 to %I64u took:%.9f\n", s, s
+>>1, (double)( end - start ) / 2394046359.0 );

    return;
}
[download]