Concerteza que já conheces o famoso quebra-cabeças chamado "Sopa de Letras" que envolve procurar palavras numa matriz cheia de letras. Pois bem, o editor de uma revista matemática resolveu criar um puzzle parecido chamado "Sopa de Primos", um problema que tem mais a ver com o tema da revista.
A ideia é termos uma matriz de algarismos e procurarmos nessa matriz quais os números primos menores ou iguais um determinado valor que aparecem. Recorda que um número primo é um número inteiro maior que um apenas divisível por um e por si próprio. Os números pode ser obtidos na horizontal (da direita para a esquerda ou da esquerda para a direita), na vertical (de cima para baixo ou de baixo para cima) ou na diagonal (também neste caso em qualquer um dos sentidos). A título de exemplo, na matriz a seguir representada podemos obter 10 primos diferentes menores que 65:
1234 1234 1234 1234 1234 1234 1234 1234 1234 1234 1234 5678 5678 5678 5678 5678 5678 5678 5678 5678 5678 5678 9888 9888 9888 9888 9888 9888 9888 9888 9888 9888 9888 Primo: 2 3 5 7 23 37 43 47 59 61
A tua tarefa é escrever um programa para resolver uma dada sopa de primos, ou seja, encontrar todos os primos menores ou iguais a um determinado valor que surgem na "sopa".
Na primeira linha do input vem um inteiro P representando o limite máximo dos números primos a considerar (0 < P ≤ 1000000). Recorda portanto que só nos interessam os primos menores ou iguais que P.
Segue-se uma linha contendo dois números inteiros separados por um espaço, L e C, que representam respectivamente o número de linhas e de colunas da matriz a considerar (0 < L,C &le 500).
De seguida vêm L linhas, cada uma contendo C dígitos (de 1 a 9), indicando a matriz propriamente dita.
O output deve ser uma lista ordenada (de forma crescente) dos primos inferiores ou iguais a P encontrados na matriz. Deve vir um número primo por cada linha.
65 3 4 1234 5678 9888
2 3 5 7 23 37 43 47 59 61