Merge Prime

MAXN = 1000000

# sieve
prime = []
table = [1 for i in range(MAXN)]
table[0] = table[1] = 0
for i in range(2,MAXN):
    if table[i] == 1:
        prime.append(i)
        for j in range(i+i,MAXN,i):
            table[j] = 0

# concatenate two primes to form a 7-digit prime. Note that they might have zeros in between.
def concatenate(p1, p2):
    length = len(str(p1) + str(p2))
    if length > 7:
        return 0
    return int(str(p1) + (7 - length) * "0" + str(p2))

ans = []    # store merge primes
for p1 in prime:
    for p2 in prime:
        merge = concatenate(p1,p2)
        if merge == 0:
            break
        if isPrime(merge):
            ans.append(merge)

ans = list(set(ans))        # remove duplicates

print sum(ans)

def isPrime(n):
    def pow(a,d,n):    # a ^ d % n
        ans = 1
        while d != 0:
            if d & 1:
                ans = (ans * a) % n
            d >>= 1
            a = (a * a) % n
        return ans

    if n < 2: return False
    if n < 4: return True
    if n % 2 == 0: return False

    s = 0
    d = n-1
    while d & 1 == 0:
        s += 1
        d >>= 1

    for i in range(50):    # higher range, higher accuracy
        a = randint(2, n-2)
        x = pow(a,d,n)
        if x == 1: continue
        for j in range(s):
            if x == n-1: break
            x = (x * x) % n
        else:
            return False
    return True

#include <stdio.h>
#include <stdbool.h>
#include <math.h>
#include <string.h>
#include <stdlib.h>

static bool prime_map[(int)1e7];

bool is_prime(int number) {
    if (number <= 1) {
        return false;
    }
    for (int i = 2; i < ((int)powf(number, 0.5) + 1); ++i) {
        if (number % i == 0) {
            return false;
        }
    }
    return true;
}

bool is_merge_prime(int number) {
    char string[11]; // max 32-bit int is 10 digits, +1 for null terminator
    sprintf(string, "%d", number);
    int num_digits = (int)strlen(string);

    char first_string[11], second_string[11];
    for (int i = 0; i < num_digits - 1; ++i) {
        int first_string_len = 0, second_string_len = 0;
        for (int j = 0; j < num_digits; ++j) {
            if (j > i) {
                second_string[second_string_len++] = string[j];
            }
            else {
                first_string[first_string_len++] = string[j];
            }
        }
        first_string[first_string_len++] = '\0';
        second_string[second_string_len++] = '\0';

        int first_number = atoi(first_string);
        int second_number = atoi(second_string);
        if (prime_map[first_number] && prime_map[second_number]) {
            //printf("%d is a merge prime because %d and %d are prime.\n", number, first_number, second_number);
            return true;
        }
    }
    return false;
}

char *suffix(char *string, int suffix_length) {
    int length = (int)strlen(string);
    if (length < suffix_length) {
        return string;
    }
    return string + length - suffix_length;
}

void build_prime_map() {
    for (int i = 0; i < (int)1e7; ++i) {
        prime_map[i] = is_prime(i);
    }
}

int main(int argc, const char * argv[]) {
    build_prime_map();

    // 4.5e6 is assuming all odd numbers are prime, obviously overkill.
    // Could use dynamic allocation instead and realloc as needed, but
    // that would be slower.
    static int seven_digit_primes[(int)4.5e6];
    int num_seven_digit_primes = 0;
    for (int i = 1e6; i < (int)1e7; ++i) {
        if (is_prime(i)) {
            seven_digit_primes[num_seven_digit_primes++] = i;
        }
    }

    static int merge_primes[(int)4.5e6];
    int num_merge_primes = 0;
    for (int i = 0; i < num_seven_digit_primes; ++i) {
        int seven_digit_prime = seven_digit_primes[i];
        if (is_merge_prime(seven_digit_prime)) {
            merge_primes[num_merge_primes++] = seven_digit_prime;
        }
    }

    uint64_t sum = 0;
    for (int i = 0; i < num_merge_primes; ++i) {
        sum += merge_primes[i];
    }

    char string[21];
    sprintf(string, "%llu", sum);
    char *last_three_digits = suffix(string, 3);
    printf("%s\n", last_three_digits);

    return 0;
}

from gmpy import is_prime
p=is_prime                  #skip if you can type is_prime faster
def mp(n):
    st=str(n)
    if not p(n):return False
    for i in range(1,len(st)):
        if p(int(st[:i])) and p(int(st[i:])):return True
    return False
su=0                         #initiate sum to 0
for i in range(1000000,9999999):
    if mp(i):su+=i
print(su%1000)