Submission #502195

---

Source Code Expand

<?php

function is_prime($n, $k) {
    if ($n == 2)
        return true;
    if ($n < 2 || $n % 2 == 0)
        return false;

    $d = $n - 1;
    $s = 0;

    while ($d % 2 == 0) {
        $d /= 2;
        $s++;
    }

    for ($i = 0; $i < $k; $i++) {
        $a = rand(2, $n-1);

        $x = bcpowmod($a, $d, $n);
        if ($x == 1 || $x == $n-1)
            continue;

        for ($j = 1; $j < $s; $j++) {
            $x = bcmod(bcmul($x, $x), $n);
            if ($x == 1)
                return false;
            if ($x == $n-1)
                continue 2;
        }
        return false;
    }
    return true;
}

function pc_permute($items, $perms, $count) {
    if (empty($items) || 5-$count >= count($items)) {
        $return = array($perms);
    }  else {
        $return = array();
        for ($i = count($items) - 1; $i >= 0; --$i) {
            $newitems = $items;
            $newperms = $perms;
            list($foo) = array_splice($newitems, $i, 1);
            array_unshift($newperms, $foo);
            $return = array_merge($return, pc_permute($newitems, $newperms, $count));
        }
    }
    return $return;
}


while(true)
{
    $stdin = trim(fgets(STDIN));
    if ($stdin === '')
        break;

    $chars = array_unique(str_split($stdin));
    $perms = pc_permute(array(1,3,5,7,9), array(), count($chars));
    $failed = true;

    if(count($chars) > 5) {
        echo "-1\n";
        continue;
    } else {
        foreach($perms as $perm){
            $num = strtr($stdin, implode('', $chars), implode('', $perm));
            if(is_prime($num, 10)) {
                $failed = false;
                echo "$num\n";
                break;
            }
        }
    }

    if($failed)
        echo "-1\n";
}

Submission Info

Judge Result