C - Print the N-esimo prime number

Question

The exercise asks the program to read an N number and print the N-esimo given prime number. Ex: I enter N = 3. The program will have to print The third prime number, which is 5. Other examples: N-esimo(2) = 3, N-esimo(5) = 11. I did the following:

void nesimo_primo(int n)
{
    int a, primo, div, nesimo;
    primo = 0;
    a = 1;
    if(n == 1)
        nesimo = 2;
    else
    {
        for(nesimo = 3; nesimo <= 1000; nesimo++)
        {
            for(div = 2; div <= nesimo/2; div++)
            {
                if(nesimo%div != 0)
                    primo++;
                if(primo == 1)
                    a = a + 1;
            }
            if(a == n)
                break;
        }
    }
    printf("N-esimo(%d) = %d\n", a, nesimo);
}

I wonder if logic makes sense and what might be wrong for the program not working properly.

Answer 1

First is to clear the values of the check variables, and knowing that the prime number is only divided by 1 and for himself, must stipulate the limit of divisions that he can make.

To catch the nth prime number, you need to check how many prime numbers have been found, so it’s good to use a counter.

Let’s start the prime number on 1 for the results to match, n3 = 5, n5 = 11. count is the counter indicating how many prime numbers have been found; rest is the sum of the rest of the entire divisions found; x is the variable to traverse the for;

int enesimo_primo(int n){
    int primo = 1;
    int count = 0;
    int rest;
    int x;

The counter, should always remain the same until you find a prime number, so you should use a while for the verification;

    while(count < n){

The prime number increment must be happening every Loop of while, and one should always be cleaning the verification variables, for a new check.

        // incremento do número primo
        primo += (primo<3) ? 1 : 2;
        rest = 0;

For checking the number if it is/is not prime, the for, because we know the limit of the number.

        for(x=1; x<=primo/2; x++){
            if(primo%x == 0) // acrescenta divisão exata
                rest+=1;
            if(rest > 1) // encerra caso o número não seja primo
                continue;
        }
        if(rest == 1) // se rest diferente de 1, o número não é primo
            count ++;
    }

Finally it remains to display the value on screen or return it.

    return primo;
}

---

main:

int main(int argc, const char **argv){
    int x = nesimo_primo(3);
    printf("%d\n", x);
    x = nesimo_primo(4);
    printf("%d\n", x);
    x = nesimo_primo(5);
    printf("%d\n", x);
    x = nesimo_primo(6);
    printf("%d\n", x);
}

saída:

5
7
11
13

Answer 2

void nesimo_primo(int n){
int a, primo, div, nesimo;

primo = 1; //primo se inicia com 1

a = 1;

if(n == 1)
    nesimo = 2;
else
{
    for(nesimo = 3; nesimo <= 1000; nesimo++)
    {
        for(div = 2; div <= nesimo/2; div++)
        {
            if(nesimo%div == 0) // se em algum momento durante o loop, a divisao der exata, sinalize q o numero nao é primo, e saia do loop
            {
                primo = 0;
                break;
            }
        }

        if(primo == 1) //se depois de passar pelo loop a flag ainda estiver ativa, faca
            a++;
        else
            primo = 1;

        if(a == n) 
            break;
    }
}
printf("N-esimo(%d) = %d\n", a, nesimo);}

The premise was correct, if you put a print on your "if(a==n)" you will see that it never entered there, if you print the cousin inside the second goes, you will see that it increases to values that are high, because you never reset the value of it.

The problem is that your cousin only calculates to the number 1000, below a different solution.

int PrimoOuNao(unsigned n){
    register int i;

    if( n == 2 )
        return 1;

    if( !(n%2) || (n == 1) )
        return 0;


    for(i = 3; i <= ceil(sqrt((double)n)); i += 2)
        if( !(n%i) )
            return 0;

    return 1;
}

unsigned Nesimo(int n){
register int i;

    if( n == 1 )
        return 2u;

    int contador = 1, primoAtual = 3;

    while( contador < n )
        if( PrimoOuNao(primoAtual++) )
            contador++;

    return --primoAtual;
}