Ca semble incroyable, avec une regexp !

<?php
 
$n = 1;
while ($n < 1000000)
    {
    if (!preg_match('/^1?$|^(11+?)\1+$/x', str_repeat('1', $n)))
        echo “$n: Prime\n”;
    $n++;
    }
?>