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