Project Euler Problem 10

Problem 10

エラトステネスの篩を使って、総和の計算をするだけ。

Schemeのコードは、Scheme:数遊び:素数列に載せられているgemmaさんのコードを参考、もとい、パクらせていただいた。

Scheme

(use srfi-1)
(use srfi-42)
(use numbers)

(define (primes n)
  (let loop ((l (unfold (lambda (x) (> x n)) values (lambda (x) (+ x 2)) 3))
             (primes-list '(2)))
    (let ((m (car l)))
      (if (> (* m m) n)
          (append primes-list l)
          (loop (remove (lambda (x) (zero? (modulo x m))) l)
                (cons m primes-list))))))

(define (p010)
  ;リストが長すぎて、applyを呼び出すとエラーが起きる……
  ;(print (apply + (primes 2000000)))
  (print (sum-ec (: i (primes 2000000)) i)))

(p010)

C++

#include <cstdio>
#include <cstring>

#define LIM 2000000
char primes[LIM+1];

void e()
{
    memset(primes, 1, sizeof(primes));
    primes[1] = 0;
    for (int i = 2; i <= LIM; i++)
        for (int j = 2*i; j <= LIM; j += i)
            primes[j] = 0;
}

int main()
{
    long long ans;

    e();
    ans = 0;
    for (int i = 1; i <= LIM; i++)
        if (primes[i])
            ans += i;

    printf("%lld\n", ans);
    return 0;
}

Project Euler Problem 9

Problem 9

a, b, cは全て自然数で、a < b < cかつa + b + c = 1000であるから、
0 < a < 1000/3, a < b < (1000-a)/2, c = 1000 - (a+b)という条件の下で調べれば良い。

証明:
a + b + c = 1000より、c = 1000 - (a+b)となり、b < cに代入すると、
b < 1000 - (a+b)
<=> b < (1000-a)/2
よって、a < b < (1000-a)/2となる。
またこれより、
a < (1000-a)/2
<=> a < 1000/3
よって、0 < a < 1000/3となる。

Scheme

(use srfi-42)

(define n 1000)
(define (p009)
  (print (car (list-ec (: a (floor (/ n 3)))
                       (: b a (floor (/ (- n a) 2)))
                       (:let c (- n a b))
                (if (eq? (+ (* a a) (* b b)) (* c c)))
                (* a b c)))))

(p009)

C++

#include <cstdio>

int main()
{
    for (int a = 1; a < 1000/3; a++)
    for (int b = a; b < (1000-a)/2; b++)
    {
        int c = 1000-(a+b);
        if (a*a+b*b==c*c) {
            printf("%d\n", a*b*c);
            goto end;
        }
    }
end:
    return 0;
}

Project Euler Problem 8

Problem 8

Schemeのコードが、すこぶる醜い。入力数値のリストを作り、先頭から5つ、二番目から5つ、,,,、(リストの要素数-4)番目から5つ、と数値を取って全ての並びを求めている。そうして求めた各リストに対して積を計算し、最大を得た。けれども並びの求め方が、醜い。もっとうまく書けそうだ。

Scheme

(use srfi-1)

(define (p008)
  (define (integer->digit c) (- c (char->integer #\0)))
  (define (input-digits)
    (let ((c (read-char)))
      (cond ((eof-object? c) '())
            ((char-numeric? c)
              (cons (integer->digit (char->integer c)) (input-digits)))
            (else (input-digits)))))
  (define (split-list ls)
    (map (lambda (x) 
           (receive (_ t) (split-at ls x)
             (take t 5)))
         (iota (- (length ls) 4))))
  (print (apply max (map (lambda (x) (apply * x)) (split-list (input-digits))))))

(p008)

C++

#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>
using namespace std;

int main()
{
    char c;
    int xs[5], ma;

    ma = 0;
    memset(xs, 0, sizeof(xs));
    while ((c = getchar()) != EOF) {
        if (!isdigit(c))
            continue;
        xs[4] = c-'0';

        int p = 1;
        for (int i = 0; i < 5; i++)
            p *= xs[i];
        ma = max(ma, p);

        for (int i = 0; i < 4; i++)
            xs[i] = xs[i+1];
    }
    printf("%d\n", ma);

    return 0;
}

Project Euler Problem 7

Problem 7

これらのプログラムでは、1から順番に素数の数を数えた。けれども、遅延評価を使ったエラトステネスの篩の方が良いかもしれない。

Scheme

(use srfi-1)

(define (prime? n)
  (if (= n 1) #f
      (let loop ((d 2))
        (cond ((> (* d d) n) #t)
              ((zero? (modulo n d)) #f)
              (else (loop (+ d 1)))))))

(define (p007)
  (let loop ((x 1) (c 0))
    (cond ((= c 10001) (print (- x 1)))
          ((prime? x) (loop (+ x 1) (+ c 1)))
          (else (loop (+ x 1) c)))))

(p007)

C++

#include <cstdio>

bool is_prime(int n)
{
    if (n == 1) return false;
    for (int i = 2; i*i <= n; i++)
        if (n%i == 0)
            return false;
    return true;
}

int main()
{
    int x, c;
    x = 1, c = 0;
    for (;;) {
        if (is_prime(x) && ++c == 10001)
            break;
        x++;
    }
    printf("%d\n", x);
    return 0;
}

Project Euler Problem 6

Problem 6

区間[1, n]の各整数の二乗の総和 = n(n+1)(2n+1)/6
区間[1, n]の各整数の総和 = n(n+1)/2

求める答えは|(n(n+1)/2)^2 - n(n+1)(2n+1)/6|となる。

Scheme

(use srfi-1)
(use numbers)

(define (square-of-sum n)
  (let ((sum (* n (+ n 1) 1/2)))
    (* sum sum)))

(define (sum-of-squares n)  
  (* n (+ n 1) (+ (* 2 n) 1) 1/6))

(define (p006)
  (print (- (square-of-sum 100) (sum-of-squares 100))))

(p006)

C++

#include <cstdio>

int square_of_sum(int n)
{
    int t = n*(n+1)/2;
    return t*t;
}

int sum_of_squares(int n)
{
    return n*(n+1)*(2*n+1)/6;
}

int main()
{
    printf("%d\n", square_of_sum(100)-sum_of_squares(100));
    return 0;
}

Project Euler Problem 5

Problem 5

この問題は、Schemeなら瞬殺。

Scheme

(use srfi-1)
(use numbers)

(define (p005)
  (print (apply lcm (iota 20 1))))

(p005)

C++

#include <cstdio>
typedef long long ll;

ll gcd(ll a, ll b)
{
    return b==0?a:gcd(b, a%b);
}

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

int main()
{
    ll l = 1;
    for (int i = 2; i <= 20; i++)
        l = lcm(l, i);
    printf("%lld\n", l);
    return 0;
}

Project Euler Problem 4

Problem 4

Scheme

(use srfi-1)
(use srfi-42)
(use numbers)

(define (number->list n)
  (define (body n)
    (if (zero? n) '()
        (cons (modulo n 10) (body (floor (/ n 10))))))
  (if (zero? n) '(0)
      (reverse (body n))))

(define (palindrome? n)
  (let ((ls (number->list n)))
    (equal? ls (reverse ls))))

(define (p004)
  (print (max-ec (: i 100 1000) (: j i 1000) (:let n (* i j))
                 (if (palindrome? n)) n)))

(p004)

C++

#include <cstdio>
#include <algorithm>
using namespace std;

bool is_palindrome(int n)
{
    int rev = 0, buf = n;
    do {
        rev = 10*rev + buf%10;
        buf /= 10;
    } while(buf != 0);
    return rev == n;
}

int main()
{
    int ma = 0;
    for (int i = 100; i < 1000; i++) {
        for (int j = i; j < 1000; j++) {
            int t = i*j;
            if (is_palindrome(t))
                ma = max(ma, t);
        }
    }
    printf("%d\n", ma);
    return 0;
}

Project Euler Problem 3

Problem 3

Scheme

(use srfi-1)

(define (prime-factors n)
  (if (= n 1) '()
      (let loop ((d 2))
        (if (zero? (modulo n d)) (cons d (prime-factors (/ n d)))
            (loop (+ d 1))))))

(define (p003)
  (print (apply max (prime-factors 600851475143))))

(p003)

C++

#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;

ll lpf(ll n)
{
    if (n == 1)
        return 1;
    for (ll d = 2;; d++)
        if (n%d==0)
            return max(d, lpf(n/d));
}

int main()
{
    printf("%lld\n", lpf(600851475143));
    return 0;
}

Project Euler Problem 2

Problem 2

Scheme

(use srfi-1)

(define (fibs)
  (let loop ((a 0) (b 1) (ls '()))
    (if (>= a 4e6) ls
        (loop b (+ a b) (cons a ls)))))

(define (p002)
  (print (apply +
                (filter (lambda (x) (zero? (modulo x 2)))
                        (fibs)))))

(p002)

C++

#include <cstdio>

int main()
{
    int a, b;
    int sum = 0;
    a = 0, b = 1;
    while (a < 4000000) {
        if (a%2 == 0)
            sum += a;
        int tmp = a;
        a = b;
        b += tmp;
    }
    printf("%d\n", sum);
    return 0;
}

Project Euler Problem 1

Problem 1

Schemeの処理系はChicken Scheme。

現状適当に表示することにしたけれど、BloggerでSchemeのコードを色付けするシンタックスハイライターってないのかしら。

Scheme

(use srfi-1)

(define (p001)
  (print (apply +
                (filter (lambda (x) (or (zero? (modulo x 3)) (zero? (modulo x 5))))
                        (iota 1000)))))

(p001)

C++

#include <cstdio>

int sum(int x, int n)
{
    int t = n/x;
    return x*t*(t+1)/2;
}

int main()
{
    printf("%d\n", sum(3, 999)+sum(5, 999)-sum(15, 999));
    return 0;
}