Project Euler #7: is anything wrong in the code?

Question

This is related to the Project Euler #7,which is about finding the 10001st prime.

In this code, if i use k*k<=i in the 2nd for loop, the program gets faster,but it gives me the 10000th prime as the answer. but when i use k<=i or k<=i/2 the program gets slower,but gives the correct answer.

according to my logic, a specific number can be divided by the numbers in the range of <1-the square root of that number>. any divisor in that range has a corresponding divisor in the range <square root - (number/2)>.

So why am i getting two various answers in this two methods???

Here's the code:

#include<stdio.h>

int main()
{
    int i;
    int k;
    int x;
    int y=0;

    for(i=1;i<100000000;i++){
        x = 0;
        /*finding whether the number has more than 2 divisor(exept 1 and the number itself)*/
        for(k=1;k*k<=i;k++){
            if(i%k == 0){
                x++;
            }
        }
        if(x==2){
            y++;
        }

        if(y == 10001){ 
            printf("\n%d",i);
            break;
        }
    }

    printf("\n\n");
    return 0;
}

Here's the other one:

#include<stdio.h>

int main()
{
    int i;
    int k;
    int x;
    int y=0;

    for(i=1;i<100000000;i++){
        x = 0;
        /*finding whether the number has more than 2 divisor(exept 1 and the number itself)*/
        for(k=1;k<=i/2;k++){
            if(i%k == 0){
                x++;
            }
        }
        if(x==1){
            y++;
        }

        if(y == 10001){ 
            printf("\n%d",i);
            break;
        }
    }

    printf("\n\n");
    return 0;
}

Answer 1

First of all, I definitely recommend doing this with Python, because it runs much faster and is much more flexible with variables.

My solution in Python for this question is similar to the algorithm you posted above, but I did it in one line thanks to Python's inline for-loops.

def isPrime(n):
     """ Determines if a number is prime """
     if n==2: return True;
     if n<2 or n%2==0: return False;
     return not any(n%i==0 for i in range(3,int(sqrt(n))+1,2));

I'm not very fluent in C, but this would look something like (someone correct my syntax if I'm wrong please):

boolean isPrime(int n) {
     if (n==2) return true;
     if (n < 2 || n % 2 == 0) return false;
     boolean r = true;
     for(int i=3;i<((int)sqrt(n))+1;i+=2) {
          if (n%i==0) r = false;
     }
     return r;
}

To find the n^th prime, simply start from 3, and increment by 2 until you find your answer.

Answer 2

You should use the Sieve_of_Eratosthenes instead, it is much faster.

Your first code will consider i=1 a prime (x==1) since for k=1: k*k <= i, but your second code will not consider it a prime, since for k=1: k > i/2. i/2 is integer divison and will be truncated to 0.