Problem #10

Calculate the sum of all the primes below two million.

Inte så elegant lösning, transportsträcka.

#include <iostream>
#include <cmath>

template <typename T>
inline bool is_prime(T p)
{
  if (p == 1)
    return false;

  if (p == 2)
    return true;

  if (!(p & 1))
    return false;

  for (T i = 2; i < sqrt(p) + 1; ++i)
    if (!(p % i))
      return false;
  return true;
}

int main(int argc, char *argv[])
{
  uint64_t prime_sum = 0;
  for (uint64_t i = 0; i < 2000000; ++i)
    if (is_prime(i))
      prime_sum += i;
  std::cout << "Answer is " << prime_sum << std::endl;
  return 0;
}

Problem #14

Här kommer min lösning till problem 14. Här stötte jag på problem då mina 32-bit int's inte räckte till på min plattform. Därav uint64_t, då talet växte till ganska stora tal (dvs större än 4294967296).

#include <iostream>
#include <utility>

template <typename T>
inline T next_seq(T n)
{
  return n & 1 ? (n * 3) + 1 : n / 2;
}

template <typename T>
inline T chain_length(T n)
{
  T i;
  for (i = 1; n != 1; ++i)
    n = next_seq(n);
  return i;
}

int main(int argc, char *argv[])
{
  std::pair<int64_t, uint64_t> chain_pair;
  for (uint64_t i = 2; i < 1000000; ++i)
  {
    uint64_t len = chain_length(i);
    if (len > chain_pair.first)
      chain_pair = std::make_pair(len, i);
  }

  std::cout << "Answer is "
            << chain_pair.first
            << " for n = "
            << chain_pair.second
            << std::endl;

  return 0;
}

Det finns en ganska bra optimering att göra in chain_length() genom att ha en hashtabell med n som nyckel och längden som värde för att inte göra onödigt jobb. Men med brute force på min MacBook går det <1s så det känns ganska onödigt.

Godnatt! Snart dags för en ny arbetsvecka.

Unix timestamp 1234567890

... har precis inträffat! Det är ett stort ögonblick. :D

Problem #8

Find the greatest product of five consecutive digits in the 1000-digit number.

Nästan för enkel:

#include <iostream>

char nums[] = {
  "73167176531330624919225119674426574742355349194934"
  "96983520312774506326239578318016984801869478851843"
  "85861560789112949495459501737958331952853208805511"
  "12540698747158523863050715693290963295227443043557"
  "66896648950445244523161731856403098711121722383113"
  "62229893423380308135336276614282806444486645238749"
  "30358907296290491560440772390713810515859307960866"
  "70172427121883998797908792274921901699720888093776"
  "65727333001053367881220235421809751254540594752243"
  "52584907711670556013604839586446706324415722155397"
  "53697817977846174064955149290862569321978468622482"
  "83972241375657056057490261407972968652414535100474"
  "82166370484403199890008895243450658541227588666881"
  "16427171479924442928230863465674813919123162824586"
  "17866458359124566529476545682848912883142607690042"
  "24219022671055626321111109370544217506941658960408"
  "07198403850962455444362981230987879927244284909188"
  "84580156166097919133875499200524063689912560717606"
  "05886116467109405077541002256983155200055935729725"
  "71636269561882670428252483600823257530420752963450"
};

int main(int argc, char *argv[])
{
  for (size_t i = 0; i < sizeof(nums); ++i)
    nums[i] -= '0'; // Just convenience

  int largest_product = 0;
  for (size_t i = 0; i < sizeof(nums) - 5; ++i)
  {
    int p = nums[i]*nums[i+1]*nums[i+2]*nums[i+3]*nums[i+4];
    largest_product = std::max(p, largest_product);
  }

  std::cout << "Answer is " << largest_product << std::endl;
  return 0;
}

Problem 7: Find the 10001st prime.

Problem #7 var lite tråkigt. Min is_prime() är inte optimal direkt. Följande fakta borde ha implementerats också:

• 1 är inte ett primtal.


• Alla primtal utom 2 är udda.


• Givet n kan bara ha en primtalsfaktor större än sqrt(n).

Min lösning:

#include <iostream>

template <typename T>
inline bool is_prime(T p)
{
  for (T i = 2; i < p; ++i)
    if (!(p % i))
      return false;
  return true;
}

int main(int argc, char *argv[])
{
  int n = 10001; 
  for (int pnum = 0, i = 2;; ++i)
  {
    if (is_prime(i))
    {
      pnum++;
      if (pnum == n)
      {
        std::cout << "Answer is " << i << std::endl;
        return 0;
      }
    }
  }
}

Godnatt!

Problem #6

Hade redan öppnat sidan för problem #6 i browsern...

#include <iostream>

template <typename T>
T sum_square(T n)
{
  T result = 0;
  for (T i = 1; i <= n; ++i)
    result += i * i;
  return result;
}

template <typename T>
T square_sum(T n)
{
  T result = 0;
  for (T i = 1; i <= n; ++i)
    result += i;
  return result * result;
}

int main(int argc, char *argv[])
{
  int n = 100;
  std::cout << "Answer is "
            << square_sum(n) - sum_square(n)
            << std::endl;
  return 0;
}

Nej, nu stänger jag av datorn för ikväll!

Problem #4

Okej, vi tar problem #4 också. Här är utmaningen att hitta det största talet som är ett palindrom genom produkten av två heltal på minst tre siffror.

#include <iostream>

template <typename T>
bool is_palindrome(T candidate)
{
  T n = candidate, rev = 0;
  while (n > 0)
  {
    rev = rev * 10 + n % 10;
    n /= 10;
  }
  return candidate == rev;
}

int main(int argc, char *argv[])
{
  int largest_palindrome = 0, cx, cy;
  int max = 1000, min = 100;
  for (int x = min; x < max; ++x)
  {
    for (int y = min; y < max; ++y)
    {
      if (is_palindrome(x * y))
      {
        int product = x * y;
        if (product > largest_palindrome)
        {
          cx = x; cy = y;
          largest_palindrome = product;
        }
      }
    }
  }
 
  std::cout << "Answer is "
            << largest_palindrome
            << " (" << cx << " * " << cy << ")"
            << std::endl;
  return 0;
}

Godnatt (på riktigt)!

Problem #3

Och här en quick'n'dirty lösning till problem #3. Här kom primtalsfaktoriseringen till användning.

#include <iostream>
#include <cmath>

template <typename T>
bool is_prime(T p)
{
  for (T i = 2; i < (p / 2.0); ++i)
    if (fmod(p, i) == 0.0)
      return false;
  return true;
}

template <typename T>
T trial_division_prime_only(T n)
{
  T max = sqrt(n), result = 0.0;
  for (T i = 2; i <= max; ++i)
    if (fmod(n, i) == 0.0 && is_prime(i))
      result = i;
  return result;
}

int main(int argc, char *argv[])
{
  long double n = 600851475143;
  std::cout << "Answer is " << trial_division_prime_only(n) << std::endl;
  return 0;
}

Godnatt!

Problem #5

En möjlig lösning till problem #5. Den här snurran tar någon sekund att beta genom på min maskin, men det går att gena genom primtalsfaktorisering fick jag lära mig.

#include <iostream>

bool f(int n)
{
  for (int i = 1; i <= 20; ++i)
    if (n % i)
      return false;
  return true;
}

int main(int argc, char *argv[])
{
  int n = 1;
  while (!f(n))
    ++n;

  std::cout << "Answer is " << n << std::endl;
  return 0;
}

Problem #2

Och här kommer lösning till problem #2:

#include <iostream>

int main(int argc, char *argv[])
{
  int sum = 0;
  for (int t, c = 2, p = 1; sum < 4000000; )
  {
    if (!(c & 1))
      sum += c;
    t = c; c += p; p = t;
  }

  std::cout << "Answer is " << sum << std::endl;

  return 0;
}

Gjorde den rekursiv först; men stacken tog lite för mycket stryk :P