7. Project Euler #7 : 10001st prime

Looking for large prime numbers obviously have to use mathematical searching prime number algorithm.

Sieve of Eratosthenes is good algorithm for finding small prime numbers.

10,001st prime number is small, so, sieve of Erotosthenes algorithm is enough.

Algorithm itself is very simple.

Hold the array space to store a few, here and put on top of each put a few on top of each.

Once a small number is odd because all but two, you can reduce the number you need to check in half.

Except for the 2, prime numbers may be expressed as follows.

Except for the 2 and 3, prime numbers may be expressed as follows.

Except for the 2, 3, and 5, prime number smay be expressed as follows.

In general, we simply check that only a minority of the Euler number. Regardless of whether the minority few excluded. But we can do to reduce the scope to do research, you can get incredibly good results with it. Excluding the 50% 2, 2, 3, excluding the 33.3%, 2, 3, 5, but when taking the long reduced to 26.6% expression, geureolsurok program complexity increases'll.

So here was to exclude minority of two. Instead, rather than to examine it all minority ever obtained, by allowing only a small number of squares is less than or equal to check if the current number, I've arranged the distinction between the different algorithms.

int main()
{
        int primes[11000];
        int count = 2;
        primes[0] = 2;
        primes[1] = 3;

        for( int i = 5 ; ; i+=2 )
        {
                int j;
                for( j = 1 ; primes[j]*primes[j] <= i ; j++ )
                        if( i%primes[j] == 0 ) break;
                if( i%primes[j] )
                {
                        primes[count++] = i;
                        if( count == 10001 ) break;
                }
        }
        printf("Ans = %d\n", primes[10000]);
}