Now we reached Problem 7 of Project Euler which is about prime numbers. The problem reads

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

What is the 10001^{st}prime number?

We could solve this by brute force checking all the numbers, or we could reuse part of the solution to problem 5, where we generated a list of primes using trial division with already found prime numbers. I haven’t found a way to solve this without finding the 10000 primes before finding the answer.

Wikipedia comes with a great article about prime numbers, which also refers to several methods for checking if a number is a prime. We will take a bit of simpler approach though. But dive into the article, it is pretty interesting.

I have found several books on prime numbers, I haven’t read any of them, but I have skimmed through Prime Numbers: The Most Mysterious Figures in Math which indeed seems very interesting, and will be on my reading list. It covers a lot of the topics that is used in Project Euler, such as abundant and perfect numbers.

## Brute Force Trial Division

I don’t want to go completely back to Adam and Eve, so the first version of the brute force algorithm uses some of the tricks, such that we only need to check up to the square root of the number to check if it is a prime. Furthermore we can exploit that all primes are odd except for 2.

First we make a small helper function called **isPrime,** which returns a boolean stating if the input number is a prime.

private bool isPrime(int numm) { if (numm <= 1) { return false; } if(numm == 2){ return true; } if (numm % 2 == 0) { return false; } int counter = 3; while ((counter * counter) <= numm) { if (numm % counter == 0) { return false; } else { counter +=2; } } return true; }

First we check if the number is even, and if not we check all odd numbers until we reach the square root of the number; Fairly simple algorithm.

Now we need the main function which counts all the primes we find until we reach the 10001^{st} prime. Once again it is straight forward.

int numPrimes = 1; int numm = 1; while (numPrimes < 10001) { numm = numm + 2; if (isPrime(numm)) { numPrimes++; } }

The first number I actually check is 3, so I have started by setting the number of primes to 1, so I remember to count 2 as well, since I never check that number to see if it a prime. Otherwise the algorithm speaks for it self I think.

Running it gives the result

Prime number 10001 is 104743 Solution took 15,625 ms

## Division with prime numbers

An alternative way to solve it, is to adapt the method in Problem 5 such that we only need to divide by known primes, in order to check if the new number is a prime. It is still using trial division, but we can limit the number of operations needed to check if a number is a prime.

The downside of this approach is that we have to store all the found primes, which in this case means storing 10001 prime numbers. The algorithm can be written as

int upperLimit = 10001; int counter = 1; bool isPrime; int j; List primes = new List(); primes.Add(2); while(primes.Count < upperLimit){ counter += 2; j = 0; isPrime = true; while (primes[j]*primes[j] <= counter) { if (counter % primes[j] == 0) { isPrime = false; break; } j++; } if (isPrime) { primes.Add(counter); } }

The algorithm uses more memory and for finding 10001 primes, there is no real difference in execution time. However if you increase the number of primes you want to find, there is a growing difference.

## Source Code

Once again I have uploaded the source code here

Table 1

Distribution of last prime digits (1, 3, 7 and 9) around

the 10 000th prime.

[Re: Project Euler 7].

http://img11.hostingpics.net/pics/218549pe7tableone.jpg

To cover the whole range of last digits (1, 3, 7 and 9) in the primes

close to 10 000, we have to extend the coverage from 9 998 to 10 004.

______

Table 2 shows that below 100, there are 5 primes ending with 1 (21.74% of the total); 7 ending with 3, (30.43% of the total), etc…

http://img11.hostingpics.net/pics/786279pe7tabletwo.jpg

Calculations done from data of ref. (4). (Base 10, primes 2 and 5 excluded from calculations).

___

Excerpt: (4)

“Despite the too low Chi-square, the prime numbers still can be regarded, according to this test, as randomly distributed.”

___

As seen in Table 2, the last digit distribution of the prime numbers is getting closer and closer to 25% as the limit is increasing in the sequence of natural numbers.

______

Sources:

1) Project Euler 7

Kristian’s algorithm

http://www.mathblog.dk/files/euler/Problem7.cs

2) Microsoft Visual C# 2010 Express

3) Microsoft Office Excel (2007)

4) Last Digit Distribution of the Prime Numbers

Are the prime numbers randomly distributed? Part 2

By Johan Gerard van der Galiën (M.Sc.) and Martin Winer.

HOME of SATOCONOR.COM

http://members.tele2.nl/galien8/digitprime/digitprime.html

int limit = 0;

int count = 1;

while(limit!=10001){

count++;

for(int i = 2;i<=count/2;i++){

if(count%i==0){

break;

}else if(i==(count/2)){

limit++;

break;

}

}

}System.out.println(count);

7 seconds 😀

0 seconds, lol! 😉

public static boolean isPrime(long n){

if(n == 2){

return true;

}

else{

for(int j=2; j*j <= n; j++){

if(n%j == 0)

return false;

}

}

return true;

}

public static void main(String[] args) {

int n = 10001;

int j = 2;

int array[] = new int[n];

for(int i = 0; i < n; i++){

if(isPrime(j))

array[i]=j;

else

i–;

j++;

}

for(int i = 0; i < n; i++){

System.out.println(i+1 +".Primzahl = " + array[i]);

}

i wrote this code in c i hope its a good one what do you think??i want

your opinionon it….What’s the time complexity of this? O(n log log n)?

Go to

http://magma.maths.usyd.edu.au/calc/

fill in

NthPrime(10001);

and press Submit.

int a[100000]={0};

for(i=2;i<100000;i++)

{

for(j=2;j

i<=100000;j++)j]=1;{

if(a[i]==0)

a[i

}

}

It’s actually fascinating that brute force solution works best. It’s my first time seeing such drama twist 🙂