How to verify which numbers of a matrix are primes?

Question

My code so far

def numerosPrimos(matrix):
lista_primos = []
for i in range(len(matrix)):
    for a in range(len(matrix[i])):
        if matrix[i][a] > 1:
            for c in range(2,matrix[i][a]):
                if matrix[i][a] % c != 0:
                    lista_primos.append(matrix[i][a])
print(f'Lista dos numeros primos da matriz: {lista_primos}')

Output:

Lista dos numeros primos da matriz: [15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 5, 5, 5, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 8, 8, 8, 8, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17]

Answer 1

To make it easier, I will exemplify with pure lists of python and not matrices, but the solution can be easily adapted to matrices.

First let’s create a function to check whether a number is prime or not:

Edited
After the observation of Pedro Herique, I changed the code of the function is_prime.
Updated also on repl it.

def is_prime(number):
    if number in [2, 3, 5, 7]:
        return True
    if number<2 or number%2==0 or number%3==0:  
        return False

    sqr = int(number**0.5)
    fact = 5
    while fact <= sqr:
        if number%fact==0 or number%(fact+2)==0: return False
        fact+=6

    return True

Now let’s define another function to filter the primes from a list:

def lst_primes(lst):
    return list(set([number for number in lst if is_prime(number)]))

Finally we will test:

lst_numbers = [73,79,83,89,97,101,103,107,109,113,127,17,19,23,25,66,73,101]
primes = lst_primes(lst_numbers)
print(primes)

Exit:

[97, 101, 103, 73, 107, 109, 79, 113, 17, 83, 19, 23, 89, 127]

See working on repl.it.

Answer 2

Sidon’s response is partially correct, but the function is_prime(n) is limited to the range 0 to 340, a function is_prime_Corrected(n) was made in the example below and demonstrates how is_prime(n) can be wrong.

Very important: there is no formula that can predict whether a number is prime other than by brute force. There are formulas that generate primes, but not all primes are generated by them! The occurrence of a prime number is totally random!

primos = []
primos2 =[]
until = 30000

def is_prime(n):
        return (2 in [n, 2**n%n] and n%3!=0) or n==3

def is_prime_Corrected(n):
    for i in range(2,n):
        if n%i == 0:
             return (False,i)
    return (n!=1),0


for n in range(1,until):
    if is_prime(n):
        primos.append(n)

for i in range(1,until):
    if is_prime_Corrected(i)[0]:
        if not is_prime(i):
            print("Embora",i,"seja um numero primo, is_prime o ignorou")
        primos2.append(i)
    elif i in primos:
            print(i,"pode ser dividido por",is_prime_Corrected(i)[1],'mas foi adicionado em "primos"')          

print(primos == primos2)

• Remarks: the is_prime function can be used to check that a number is not prime (using not is_prime(n)) and to speed up processing to at least 30,000, maybe more