Project Euler – Problem 7

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)) {

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();


while(primes.Count < upperLimit){
    counter += 2;
    j = 0;
    isPrime = true;
    while (primes[j]*primes[j] <= counter) {
        if (counter % primes[j] == 0) {
            isPrime = false;
    if (isPrime) {

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

Posted by Kristian


Jean-Marie Hachey

Table 1
Distribution of last prime digits (1, 3, 7 and 9) around
the 10 000th prime.
[Re: Project Euler 7].

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…

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.



1) Project Euler 7
Kristian’s algorithm
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.

int limit = 0;
int count = 1;
for(int i = 2;i<=count/2;i++){
}else if(i==(count/2)){

7 seconds 😀

0 seconds, lol! 😉

public static boolean isPrime(long n){
if(n == 2){
return true;
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++){

for(int i = 0; i < n; i++){
System.out.println(i+1 +".Primzahl = " + array[i]);

harry hadrian kione

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;

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

Go to

fill in


and press Submit.

satya shivam

int a[100000]={0};


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

The brute force method is confusing…. what would happen if the number to test if it is a prime number or not is 21 or 15

Leave a Reply