Project Euler – Problem 7

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.

What is the 10 001st prime number?

#include <cstdio>
#include <cstring>

#define MAX 1000000
bool p[MAX];
int main(void){

	memset(p, 1, sizeof(p));
	int ans = 1000, c = 1;
	for(int i = 4; i < MAX; i += 2) p[i] = 0;
	for(int i = 3; i < 1001; i += 2)
		if(p[i]){
			++c;
			for(int j = i * i; j < MAX; j += i) p[j] = 0;
		}
		while(c < 10001) c += p[++ans];

		printf("Answer: %d\n", ans);
		return 0;
}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s