Você testou o seu código com alguns casos?
Por exemplo, se o número for 9, vamos imaginar.
Não vai passar pelo primeiro if
, pois 9 == 2
é falso
O segundo elif vai testar:
num = 9
# 9 % 2 é 1
# 9 == 1 é falso
Logo, não vai cair na condição e vai printar que o número é primo mesmo que 9 não seja um número primo.
Sobre números primos, todos os números primos maiores que 3 tem uma fórmula: 6n +/- 1
Você pode encontrar uma discussão sobre a prova desse conceito aqui
Sabendo isso, fica mais fácil de pensar em um algoritmo. Não quero te dar a resposta pra vc pensar sozinho, mas vou deixar algumas referências:
https://en.wikipedia.org/wiki/AKS_primality_test
Se você tiver alguma dúvida, comenta que volto para ajudar. Bons estudos