Prime numbers in C

Question

I started programming recently and soon they gave me the problem of creating an algorithm to check whether a number is prime or not. As at the time I was still having some difficulty in looping repetitions, I created an if/Else-based algorithm to solve the problem:

#include <stdlib.h>
#include <stdio.h>
int main(void)
{
    int a; 
    scanf("%d",&a);
             if(((((a % 2 == 0) and (a != 2))
             or ((a % 3 == 0) and (a != 3)))
             or (((a % 5 == 0) and (a != 5)) 
             or ((a % 7 == 0) and (a != 7)))) )
             {

             }
             else
             {
               printf("%d ", a);
             }


    return 0;
}

The algorithm even checks whether a number is prime or not, but when the factorization of a number is the multiplication of two prime numbers such as 169 (13*13) or 143 (11*13), the number also passes as prime. I used the Math. h library to compute the root of the number and exclude it when it is a square of a prime number:

#include <stdlib.h> 
#include <stdio.h> 
#include <math.h>

int main(void)
{
    int a;
    float c, b;
    scanf("%d", &a);
    c = a;
    b = sqrt(c) ;
    if (a == 1)
    {
          printf("o numero 1 nao eh primo");
    }
   if((((((a % 2 == 0) and (a != 2))
   or ((a % 3 == 0) and (a != 3)))
   or (((a % 5 == 0) and (a != 5)) or ((a % 7 == 0) and (a != 7)))) or floor(b) == b ))
    {
          printf("Nao eh primo\n\n\n");
    }
    else
    {
        printf("%d eh primo\n\n\n", a);
    }
    return 0;
}

But I haven’t been able to solve numbers that have the same case of 143, my doubt is as if I can verify if a number is prime or not without use loop loops. Thank you :)

Answer 1

I think this would be an interesting basis for what you want.

You do not need to test all the values, because if up N/2 is not divisible, from there it is divisible only by itself.

#include <stdio.h>

void chama_primo(int valor);
int checa_primo(int qtd_divisor, int value, int divisor);

int main() {

    int num;

    scanf("%d", &num);

    chama_primo(num);

    return 0;
}

void chama_primo(int valor) {

    if(checa_primo(0, valor, 2)) {
        printf("Número é primo\n");
    }
    else {
        printf("Não é primo\n");
    }
}

int checa_primo(int qtd_divisor, int value, int divisor) {

    int aux = qtd_divisor;

    if(qtd_divisor > 0) {
        return 0;
    }

    if(divisor > (value/2) && qtd_divisor == 0) {
        return 1;
    }

    if(value % divisor == 0) {
        aux++;
    }

    return checa_primo(aux, value, divisor+1);
}

I even tested N = 23 and all right.

Answer 2

Good is not more elegant code that exists ,but solves the problem well with a little recursion.

Code

#include <stdio.h>
#include <stdbool.h>

bool ePrimo(int n ,int nn);

int main(void)
{
  int n = 0;
  
  printf("Digite um numero: ");
  scanf("%d" ,&n);
  if (ePrimo(n ,1))
    printf("%d e primo!" ,n);
  else
    printf("%d nao e primo!" ,n);
  
  return 0;
}

bool ePrimo(int n ,int nn)
{
  static int divs = 0;
  
  if (nn > n)
    return n;
  
  if (n % nn == 0)
    divs++;
  
  ePrimo(n ,nn + 1);
  
  if (divs <= 2)
    return 1;
  return 0;
}

If you need any explanation ,here I am.