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;
}