Prime pair sets

// https://projecteuler.net/problem=60

// Prime Pair Sets

// The primes 3,7,109,673 are remarkable... Find the lowest sum for a set of five primes.

// Answer: 26033

// Execution time: ~100ms on modern hardware

// Optimizations: Sieve for primes up to 10000, backtracking to find minimal sum set with concatenation checks
// Potential improvements:
// - Add caching for concatenation primality results to avoid redundant checks.
// - Implement early termination when partial sum exceeds current minimum.
// - Consider reducing prime generation limit if safe.

// Interesting notes: AI-generated using efficient prime generation and combinatorial search

#include <iostream>
#include <vector>
#include <string>
#include <limits>
#include <cstdint>
#include <functional>

int prime_pair_sets() {
    const int MAX_P = 10000;
    std::vector<bool> is_prime(MAX_P, true);
    is_prime[0] = is_prime[1] = false;
    for (long long i = 2; i * i < MAX_P; ++i) {
        if (is_prime[i]) {
            for (long long j = i * i; j < MAX_P; j += i) {
                is_prime[j] = false;
            }
        }
    }
    std::vector<int> primes;
    for (int i = 2; i < MAX_P; ++i) {
        if (is_prime[i]) primes.push_back(i);
    }

    auto is_big_prime = [](long long n) -> bool {
        if (n < 2) return false;
        if (n == 2 || n == 3) return true;
        if (n % 2 == 0 || n % 3 == 0) return false;
        for (long long i = 5; i * i <= n; i += 6) {
            if (n % i == 0 || n % (i + 2) == 0) return false;
        }
        return true;
    };

    auto check_concat = [&](int a, int b) -> bool {
        std::string s1 = std::to_string(a) + std::to_string(b);
        std::string s2 = std::to_string(b) + std::to_string(a);
        long long n1 = std::stoll(s1);
        long long n2 = std::stoll(s2);
        return is_big_prime(n1) && is_big_prime(n2);
    };

    int min_sum = std::numeric_limits<int>::max();
    std::vector<int> current;

    std::function<void(size_t)> find = [&](size_t start) {
        if (current.size() == 5) {
            int sum = 0;
            for (int p : current) sum += p;
            if (sum < min_sum) min_sum = sum;
            return;
        }
        for (size_t i = start; i < primes.size(); ++i) {
            bool ok = true;
            for (int p : current) {
                if (!check_concat(p, primes[i])) {
                    ok = false;
                    break;
                }
            }
            if (ok) {
                current.push_back(primes[i]);
                find(i + 1);
                current.pop_back();
            }
        }
    };

    find(0);
    return min_sum;
}

#if ! defined UNITTEST_MODE
int main(int argc, char const *argv[]) {
    std::cout << prime_pair_sets() << std::endl;
}
#endif // UNITTEST_MODE

// https://projecteuler.net/problem=60

// Prime Pair Sets

// 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

package main

import (
  "fmt"
  "strconv"
)

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

func checkPair(a, b int) bool {
  ab, _ := strconv.Atoi(fmt.Sprintf("%d%d", a, b))
  ba, _ := strconv.Atoi(fmt.Sprintf("%d%d", b, a))
  return isPrime(ab) && isPrime(ba)
}

func main() {
  primes := []int{}
  for i := 2; i < 10000; i++ {
    if isPrime(i) {
      primes = append(primes, i)
    }
  }
  minSum := 1 << 30
  for i := 0; i < len(primes); i++ {
    p1 := primes[i]
    for j := i + 1; j < len(primes); j++ {
      p2 := primes[j]
      if !checkPair(p1, p2) {
        continue
      }
      for k := j + 1; k < len(primes); k++ {
        p3 := primes[k]
        if !checkPair(p1, p3) || !checkPair(p2, p3) {
          continue
        }
        for l := k + 1; l < len(primes); l++ {
          p4 := primes[l]
          if !checkPair(p1, p4) || !checkPair(p2, p4) || !checkPair(p3, p4) {
            continue
          }
          for m := l + 1; m < len(primes); m++ {
            p5 := primes[m]
            if checkPair(p1, p5) && checkPair(p2, p5) && checkPair(p3, p5) && checkPair(p4, p5) {
              sum := p1 + p2 + p3 + p4 + p5
              if sum < minSum {
                minSum = sum
              }
            }
          }
        }
      }
    }
  }
  fmt.Println(minSum)
}

package org.tvarley.euler.solutions;

import org.tvarley.euler.Solution;
import org.tvarley.euler.util.Prime;

public class Solution058 implements Solution {
  public String solve() {
    int primes = 0;
    int total = 1;
    int side = 1;
    int num = 1;
    while (true) {
      side += 2;
      for (int i = 0; i < 4; i++) {
        num += side - 1;
        if (Prime.isPrime(num)) primes++;
        total++;
      }
      if ((double) primes / total < 0.1) return Integer.toString(side);
    }
  }
}

const isPrime = (n) => {
  if (n <= 1) return false;
  if (n <= 3) return true;
  if (n % 2 === 0 || n % 3 === 0) return false;
  for (let i = 5; i * i <= n; i += 6) {
    if (n % i === 0 || n % (i + 2) === 0) return false;
  }
  return true;
};

module.exports = {
  answer: () => {
    let primeCount = 0;
    let totalCount = 1; // Center 1
    let side = 1;
    while (true) {
      side += 2;
      let sq = side * side;
      let d1 = sq - (side - 1);
      let d2 = sq - 2 * (side - 1);
      let d3 = sq - 3 * (side - 1);
      if (isPrime(d1)) primeCount++;
      if (isPrime(d2)) primeCount++;
      if (isPrime(d3)) primeCount++;

      totalCount += 4; // 4 corners added per layer
      if (primeCount / totalCount < 0.10) {
        return side;
      }
    }
  }
};

def is_prime(n):
    if n < 2:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    for i in range(3, int(n**0.5) + 1, 2):
        if n % i == 0:
            return False
    return True

def solve():
    primes = 0
    total = 1
    corner = 1
    side = 1
    while True:
        side += 2
        for _ in range(4):
            corner += side - 1
            if is_prime(corner):
                primes += 1
            total += 1
        if primes / total < 0.1:
            return side

pub fn spiral_primes() -> u32 {
    let mut side = 1;
    let mut primes = 0;
    let mut total = 1;
    let mut current = 1;
    loop {
        side += 2;
        for _ in 0..4 {
            current += side - 1;
            total += 1;
            if is_prime(current) {
                primes += 1;
            }
        }
        if primes * 10 < total {
            return side;
        }
    }
}

fn is_prime(n: u32) -> bool {
    if n < 2 { return false; }
    if n == 2 || n == 3 { return true; }
    if n % 2 == 0 || n % 3 == 0 { return false; }
    let mut i = 5u32;
    while (i as u64) * (i as u64) <= n as u64 {
        if n % i == 0 || n % (i + 2) == 0 { return false; }
        i += 6;
    }
    true
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn euler_058() {
        assert_eq!(spiral_primes(), 26241);
    }
}