Finding prime numbers

[stdq]

Hi, I wrote a code to check all the primes between 2 and 1002, but I for each nth number tested, I go from 2 to n-1. By running the program, I got 168 numbers, which is correct according to a website. However, I've read it that I only need to check until the square root of n, but I tried making that change in the inner for loop by choosing j < sqr(i), and it just finds the number 2 as a prime. Why is this happening? Thanks in advance!

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

void primeFinder(void);

int main(void)
{
    printf("Prime numbers from 1 to 1000:\n\n");
    primeFinder();

    return 0;
}


void primeFinder(void)
{
    int i;
    int j;
    int k;
    int n_primes = 0;

    //i is the number to be tested:
    for ( i = 2 ; i <= 1000 ; i++ )
    {
        //i must be divided by j, that goes from 2 to i - 1 [(i - 2) divisions]:
        for ( j = 2, k = 0 ; j < i ; j++ )
        {
            //i is not prime, whatever is the value of j:
            if ( i % j == 0 )
            {
                //If remainder is 0, there is no need to test that i anymore:
                break;
            }
            else
            {
                k++;
            }

        } //End of inner for
        //i is prime:
        if ( k == i - 2 )
        {
            printf("%d\t", i);
            n_primes++;
        }
    } //End of outer for
    printf("\n\nIt was found %d prime(s) in the inverval considered.\n", n_primes);
}

[laserlight]

I tried making that change in the inner for loop by choosing j < sqr(i), and it just finds the number 2 as a prime. Why is this happening?

Look carefully at the condition by which you finally decide whether to print the number as prime:

if ( k == i - 2 )

Does it tally with your introduction of sqrt(i)?

By the way, why do you need k when you already have j?

[anduril462]

Take i = 49 for an example. 7*7 = 49, so it's composite. But if you only check j < sqrt(i), you only check divisors from 2 through 6, which would incorrectly report 49 as prime. You need to go until j <= sqrt(i).

[stdq]

Thanks, laserlight and anduril462. I've now managed to improve the program by checking only until the square root of each number.