Project Euler Code Cheat Sheet

From Stack Overflow
Jump to: navigation, search

Contents

Project Euler starter

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
//#include <math.h>
//#include <ctype.h>
//#include <gmp.h>
/*
 *
 */

void test()
{
}

int main(int argc, char **argv)
{
    test();
    return 0;
}

isPrime

isPrime : unsigned int

int isPrime(unsigned int value)
{
    unsigned int max;
    // Fail by definition (prime has to be > 1)
    if (value <= 1)
        return 0;
    if (value == 2)
        return 1;
    // Check if prime
    max = sqrt(value) + 1;
    for (unsigned int i = 2; i <= max; i++)
        if ((value % i) ==  0)
            return 0;
    return 1;
}

isPrime : bignum

int isPrime(mpz_t n)
{
    mpz_t iterator;
    mpz_t maxIterator;
    mpz_t remainder;

    if (mpz_cmp_ui(n, 1) <= 0) // negatives, zero, 1 : not prime
        return 0;
    if (mpz_cmp_ui(n, 2) == 0) // 2 : prime
        return 1;
    mpz_init(remainder);
    mpz_init(iterator);
    mpz_init(maxIterator);
    mpz_sqrt(maxIterator, n);
    mpz_add_ui(maxIterator, maxIterator, 1); // round up
    for (mpz_set_ui(iterator, 2); mpz_cmp(iterator, maxIterator) <= 0; mpz_add_ui(iterator, iterator, 1))
    {
        mpz_cdiv_r(remainder, n, iterator);
        if (mpz_cmp_ui(remainder, 0) == 0)
            return 0;
    }
    return 1;
}

Permutations

void printCallback(char *s)
{
    printf("%s\n", s);
}

int doPermutations(char *charset, int charsetLength, char depth, char *buffer, void (*callback)(char *))
{
    char *bufferEnd = buffer + strlen(buffer);
    if (depth == 0)
    {
        callback(buffer);
    }
    for (int i = 0; i < charsetLength; i++)
    {
        if (*(charset + i) != 0)
        {
            char c = *(charset + i);
            *(charset + i) = 0;
            *bufferEnd = c;
            *(bufferEnd + 1) = '\0';
            doPermutations(charset, charsetLength, depth - 1, buffer, callback);
            *bufferEnd = '\0';
            *(charset + i) = c;
        }
    }
    return 0;
}
Personal tools