Project Euler – Problem 7

Written by on 3 November 2010

Topics: Project Euler

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 6th prime is 13.

What is the 10001st 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 10001st 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<int> primes = new List<int>();

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

5 Comments For This Post I'd Love to Hear Yours!

  1. Jean-Marie Hachey says:

    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

  2. Cyril says:

    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 😀

  3. causal says:

    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]);
    }

  4. harry hadrian kione says:

    i wrote this code in c i hope its a good one what do you think??i want your opinion on it….

    #define max 104745
    int main(void)
    {
    	int arr[max];
    	int counter=0;
    	int i,j;
    	for(i=0;i&lt;max;i++)
    	{
    		arr[i]=1;
    	}
    	for(i=2;i&lt;max;i++)
    	{
    		if(arr[i]==1)
    		{
    			counter++;
    			if(counter==10001)
    			{
    				printf(&quot;%lld&quot;,i);
    				exit(0);
    			}
    			for(j=i+i;j&lt;max;j+=i)
    			{
    				arr[j]=0;
    			}
    			
    		}
    	}
    }
    
  5. Anon says:

    What’s the time complexity of this? O(n log log n)?

Leave a Comment Here's Your Chance to Be Heard!

You can use these html tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

You can use short tags like: [code language="language"][/code]

The code tag supports the following languages: as3, bash, coldfusion, c, cpp, csharp, css, delphi, diff,erlang, groovy, javascript, java, javafx, perl, php, plain, powershell, python, ruby, scala, sql, tex, vb, xml

You can use [latex]your formula[/latex] if you want to format something using latex

This site uses cookies.