Problema em linguagem C

Código:

#include <stdio.h>

int main()
{
    //Supondo um intervalo fechado [n1,n2]
    int n1,n2;

    scanf("%d %d",&n1,&n2);

    int i = n1;

    while(i != n2+1)
    {
        int j = 2;

        if(i == 2)
            printf("2 ");
        else if(i != 1)
        {
            while(j*j <= i) //******//
            {
                if(i % j == 0)
                {
                    j = -1; // Logo, NÂO PRIMO
                    break; //quebrando o while
                }
                j++;
            }
            if(j != -1)
                printf("%d ",i);
        }
        i++;
    }

    return 0;
}


Melkor256 escreveu:

Código:

#include <stdio.h>

int main()
{
    //Supondo um intervalo fechado [n1,n2]
    int n1,n2;

    scanf("%d %d",&n1,&n2);

    int i = n1;

    while(i != n2+1)
    {
        int j = 2;

        if(i == 2)
            printf("2 ");
        else if(i != 1)
        {
            while(j*j <= i) //******//
            {
                if(i % j == 0)
                {
                    j = -1; // Logo, NÂO PRIMO
                    break; //quebrando o while
                }
                j++;
            }
            if(j != -1)
                printf("%d ",i);
        }
        i++;
    }

    return 0;
}


Na linha com vários asteriscos há também a possibilidade de parar somente quando j < i, while(j < i). Contudo, da forma que eu fiz o tempo de execução deixa do laço deixa de ser N-1 e passa a ser sqrt(N);

Lembrando, se N é um número composto (Não primo) então esse possui algum divisor d <= sqrt(N)!

Ex.: N = 9 = 3 * 3, possui um divisor d <= sqrt(9) <= 3, d pertence a {1,2,3}
Ex.: N = 7, não é possível fatorá-lo em com mais de um número primo, logo, não existe um divisor d <= sqrt(7)
Ex.: N = 3,  Idem
Ex.: N = 10 = 2 * 5 .:. Existe um d <= sqrt(10), d pertence a {1,2,3}