Project Euler Problem 60

Problem 60

02 January 2004

The primes 3, 7, 109, and 673, are quite remarkable. By taking any two primes and concatenating them in any order the result will always be prime. For example, taking 7 and 109, both 7109 and 1097 are prime. The sum of these four primes, 792, represents the lowest sum for a set of four primes with this property.

Find the lowest sum for a set of five primes for which any two primes concatenate to produce another prime.

Answer: 26033

Solution in C#

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

namespace Euler {

    class Problem60 {

        static HashSet<int> primesUnder(int limit) {

            var p = new bool[limit];

            if (limit >= 3) p[2] = true;

            for (int i = 3; i < limit; i += 2) p[i] = true;

            for (int i = 3; i * i < limit; i += 2) {

                if (!p[i]) continue;

                for (int j = i + i; j < limit; j += i)

                    p[j] = false;

            }

            var r = new HashSet<int>();

            for (int i = 2; i < limit; i++)

                if (p[i]) r.Add(i);

            return r;

        }

        static bool isPrime(int value) {

            if (value <= 1) return false;            

            for (int i = 2; i * i <= value; i++) {

                if (value % i == 0) return false;

            }

            return true;

        }

        static bool isConcatPrime(int a, int b) {

            return isPrime(Convert.ToInt32(a.ToString() + b.ToString())) &&

                isPrime(Convert.ToInt32(b.ToString() + a.ToString()));

        }

        static int[] primes;

        public static void run() {

            primes = primesUnder(10000).ToArray();

            

            for (var i0 = 0; i0 < primes.Length; i0++) {

                for (var i1 = i0 + 1; i1 < primes.Length; i1++) {

                    if (!isConcatPrime(primes[i0], primes[i1])) continue;

                    for (var i2 = i1 + 1; i2 < primes.Length; i2++) {

                        if (!isConcatPrime(primes[i0], primes[i2])

                            || !isConcatPrime(primes[i1], primes[i2])

                            ) continue;

                        for (var i3 = i2 + 1; i3 < primes.Length; i3++) {

                            if (!isConcatPrime(primes[i0], primes[i3])

                                || !isConcatPrime(primes[i1], primes[i3])

                                || !isConcatPrime(primes[i2], primes[i3])

                            ) continue;

                            for (var i4 = i3 + 1; i4 < primes.Length; i4++) {

                                if (!isConcatPrime(primes[i0], primes[i4])

                                    || !isConcatPrime(primes[i1], primes[i4])

                                    || !isConcatPrime(primes[i2], primes[i4])

                                    || !isConcatPrime(primes[i3], primes[i4])

                            ) continue;

                                Console.WriteLine(primes[i0] +

                                    primes[i1] +

                                    primes[i2] +

                                    primes[i3] +

                                    primes[i4]);

                                return;

                            }

                        }

                    }

                }

            }

        }

    }

}

Solution in Go

 

 

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

 

func primesUnder(limit int) []int {
    p := make([]bool, limit)
    if limit >= 3 {
        p[2] = true
    }
    for i := 3; i < limit; i += 2 {
        p[i] = true
    }
    for i := 3; i*i < limit; i += 2 {
        if !p[i] {
            continue
        }
        for j := i * 2; j < limit; j += i {
            p[j] = false
        }
    }

    r := []int{}
    for i := 2; i < limit; i++ {
        if p[i] {
            r = append(r, i)
        }
    }
    return r
}

func isConcatPrime(a int, b int) bool {
    c1,_ := strconv.Atoi(strconv.Itoa(a)+strconv.Itoa(b))
    c2,_ := strconv.Atoi(strconv.Itoa(b)+strconv.Itoa(a))
    return isPrime(c1) &&
        isPrime(c2)
}

func problem60() {
    primes := primesUnder(10000)

    for i0 := 0; i0 < len(primes); i0++ {
        for i1 := i0 + 1; i1 < len(primes); i1++ {
            if !isConcatPrime(primes[i0], primes[i1]) {
                continue
            }
            for i2 := i1 + 1; i2 < len(primes); i2++ {
                if !isConcatPrime(primes[i0], primes[i2]) || !isConcatPrime(primes[i1], primes[i2]) {
                    continue
                }
                for i3 := i2 + 1; i3 < len(primes); i3++ {
                    if !isConcatPrime(primes[i0], primes[i3]) ||
                        !isConcatPrime(primes[i1], primes[i3]) ||
                        !isConcatPrime(primes[i2], primes[i3]) {
                        continue
                    }
                    for i4 := i3 + 1; i4 < len(primes); i4++ {
                        if !isConcatPrime(primes[i0], primes[i4]) ||
                            !isConcatPrime(primes[i1], primes[i4]) ||
                            !isConcatPrime(primes[i2], primes[i4]) ||
                            !isConcatPrime(primes[i3], primes[i4]) {
                            continue
                        }
                        fmt.Println(primes[i0] +
                            primes[i1] +
                            primes[i2] +
                            primes[i3] +
                            primes[i4])
                        return
                    }
                }
            }
        }
    }
}

func main() {
    problem60()
}