10001st Prime Number

[Idiotal]

Hello, I've been trying to solve project euler problem #7, it is to find the 10,001st Prime Number, that is the code I am trying :-

#include <iostream>
int main(){
	int z = 0;
	int n = 0;
	while (z <= 10001){
		for (n = 0; z <= 10001; n++){
			for (int divisor = 0; divisor <= n; divisor++){
				if (n%divisor != 0){
					std::cout << n << std::endl;
					z++;

				}
			}
		}
	}
}

But Visual Studio gives me an error: An unhandled Win32 exception occured in (programName).exe, and I can't seem to figure out what's wrong, any help?

[cire]

On line 8 you're dividing by 0.

[fredk]

Even fixing the line 8 problem, your algorithm is incorrect - you increment z way too often. . Try it out by hand to find the 4th prime (7). Figure out a correct algorithm before you even write one line of code. Then figure out whether there is anything you can do to speed it up. For example, you are checking every divisor from 0 to n. Obviously there is no need for 0 or 1. Also true is that you don't need to check for any divisor greater than the square root of n, and you don't need to check any even divisors after 2.

[TheIdeasMan]

Hi,

The main idea of Euler Project is to come up with clever ways of achieving the result, brute force is not the answer. The scale of the problem usually means that naive ideas won't work. If you are doing problem #7, you should have dealt with primes several times now, and your current design would not have worked well for them. It is a good idea to do the problems in order, things learnt in earlier problems help a lot with the later ones.

A better algorithm is to start out with all the numbers. The first prime is 2, so remove all multiples of it. Now the next number on the list is 3, so remove all multiples of that. Next is 5, 7, 11 ..... The size of the list reduces quickly. std::bitset can be used, the subscript is the number, set that position to true or false depending on whether it is prime or not.

There are other algorithms which are even better: Atkins comes to mind, but that is a little more involved.

[Arslan7041]

Aside from sieving (which is what TheIdeasMan is suggesting), you can simply do primality testing.

Make a function called isPrime that takes some number N, and returns true if its prime and false otherwise. You can call that function from main in a loop, and increment a counter variable every time the return value is true. Once the counter reaches 10,001 simply break out of the loop and print the number.

The isPrime function will have a loop that checks all divisors less than N (the number passed into the function).

Pseudocode below:

main()
{
   int   i=0;
   while(primes <10001)
       if isPrime(i) returns true, primes++
       i++; // increment i to test if the next number is prime
)

bool isPrime(int N)
{
      if N is less than 2, return false;
      for(i=2  to N)
           if i divides evenly into N, return false

      return true

This is the most basic algorithm. You can optimize it by only passing odd numbers ('i' is incremented by 2 instead of 1) to the isPrime function, as all primes are odd (except for 2, which is a special case). You can further optimize the isPrime function by looping up to sqrt(N) instead of N. And you can even further optimize by checking only odd divisors.

There are further optimizations but I'll leave those for you to figure out.

[TheIdeasMan]

@Arslan7041

That isn't really any more efficient than what the OP is doing (yours calls a function to do the same thing), the problem is line 13, one is going through all the numbers again. Not doing odd numbers isn't much of an optimisation: consider what happens if one wants all the primes less than a relatively small number - 1 billion say. Looping up to sqrt of limit isn't an option, the problem requires 10001 primes, the value of that number is unknown.

One can test the efficiency of the algorithm by timing it. test with numbers up to 1'000, 20'000, 50'000, 100'000, 500'000 etc. If the algorithm takes longer than 1 second there is definitely something wrong, a good algorithm can do it faster than that.

There are primal testing algorithms used used for large numbers, but those are vastly different. There is unsurprisingly lots of info with Google and wiki.

https://en.wikipedia.org/wiki/Primality_test

[Arslan7041]

@TheIdeasMan: I think you've either misunderstood my algorithm, or I didn't explain it well enough. The algorithm I described is significantly more efficient than what the OP has in the first post, at least enough to solve the problem quickly.

The idea is to keep finding primes in order, until the 10001st prime. In order to do that, you send all odd numbers to the isPrime function, and (after taking care of special cases like 2) loop up to the square root of that odd number, looking for any divisors. What do you mean by "value of that number is unknown"?

Here is the full implementation

#include <iostream>
#include <ctime>
#include <cstdlib>
#include <cmath>

bool isPrime(int);
int main()
{
    while(true)
    {
        int primes = 2;
        int i = 5, N;
        clock_t start, stop;

        std::cout << "Enter the Nth prime number you want: ";
        std::cin >> N;

        start = std::clock();
        while(true)
        {
            if(isPrime(i)) primes++;
            if(primes == N) break;
            i+=2;
        }
        stop = std::clock();

        std::cout << "The " << N << "th prime is: " << i << "\n";
        std::cout << "Duration = " << (stop-start)*1000./CLOCKS_PER_SEC << " milliseconds\n\n";
    }

   return 0;
}

bool isPrime(int n)
{
    if(n<2) return false;
    if(n<=3) return true;
    if(n%2==0) return false;
    if(n<9) return true; // n can only be 5 or 7 at this point
    if(n%3==0) return false;

    for(int i=5; i<=sqrt(n); i+=2)
    {
        if(n%i==0)return false;
    }

    return true;
}

One can test the efficiency of the algorithm by timing it. test with numbers up to 1'000, 20'000, 50'000, 100'000, 500'000 etc. If the algorithm takes longer than 1 second there is definitely something wrong, a good algorithm can do it faster than that.

Found the 10,001st prime in 64 milliseconds.
An even more optimized version of this code found the 10,001st prime in 25 milliseconds. But I will leave that implementation for the OP, or other readers to figure out.

On the contrary, I would not recommend the sieving method you described. This is because:

(1) This is a primality test problem, not a sieving problem. In sieving, the algorithm gives you all primes numbers up to N. Here we want the Nth prime number. So this doesn't work here, because you dont know how large your list needs to be.

(2) Sieve of Eratosthenes is spatially inefficient unlike the algorithm I described.

[JLBorges]

> You can further optimize the isPrime function by looping up to sqrt(N) instead of N.

>> Looping up to sqrt of limit isn't an option, the problem requires 10001 primes, the value of that number is unknown.

For the nth prime number, denoted by p_n:
( log n + log log n - 1 ) < ( p_n / n ) < ( log n + log log n ) for n >= 6
https://en.wikipedia.org/wiki/Prime_number_theorem#Approximations_for_the_nth_prime_number

Spoiler: http://coliru.stacked-crooked.com/a/bfbda98320d65f50

[TheIdeasMan]

Just going back to this again :+)

The algorithm I described is significantly more efficient than what the OP has in the first post, at least enough to solve the problem quickly.

Yes it is, and it does, and it seems OK for small numbers, but it is not as good as Eratosthenes. That can be seen from JLBorges' code. In comparison, using cpp.sh, at N = 600'000 the time taken was 3225ms, at 650'000 it seemed to time out?.

(1) This is a primality test problem, not a sieving problem. In sieving, the algorithm gives you all primes numbers up to N. Here we want the Nth prime number. So this doesn't work here, because you dont know how large your list needs to be.

But your code isn't really a primality "test": it still works out all the primes (on line 46, n is prime), just they are not being displayed or stored. As an example, my idea of a test is something like the remainder theorem for polynomials. If one plugs a number N into the polynomial formula, and the result is 0, then (x-N) is a factor. If one were to try all the integers from -10 to 10, then that becomes an algorithm that uses a test repeatedly.

Your code is similar to Eratosthenes Sieve in a lot of ways: the limit of sqrt(N), only doing odd numbers, some short circuiting when a factor is found. On the face of it, it might even look similar in performance, but it isn't really. It's worth noting that the sqrt of the 10'001 prime is only 323, so we are dealing with small numbers here.

However your code is still a type of trial division: if(n%i==0)return false;. This is almost the same as setting values to false in a std::bitset. Where it differs is that yours tests multiples of 3 when 3 isn't a factor. For example, for a sufficiently large number that isn't a multiple of 3, it stills tests whether 9, 15, 21 .... are factors. These tests are repeated for successive primes. This is different to Eratosthenes because, in that, multiples are removed once.

This leads to Eratosthenes, or more specifically Euler's Sieve. One can use a std::bitset and the subscript as the number, then set positions in the to false if it isn't prime.

https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

An advantage of using std::bitset is that addition is used with the subscript, there is no modulus operation. JLBorges's code does that too.

(2) Sieve of Eratosthenes is spatially inefficient unlike the algorithm I described

There are segmented versions of Eratosthenes that use much less memory. Yours doesn't use memory because it doesn't store anything :+)

One might as well store the primes, then it is much cheaper on successive occasions to do a lookup. For example if one found the N'th prime, then wanted something less than the N'th prime, do a lookup.

Regards :+)

[Arslan7041]

I see what you are saying, but I was speaking specifically with regards to this problem, which is why I still think using sieve of Eratosthenes is a bit of overkill here. The problem specifically intends one to use a "repeated primality test" as my algorithm does, which is why it asks for the Nth prime number, and not "all primes up to N" as sieving does. This is also why JLBorges had to find an upper-bound for the Nth prime number first.

And I agree, in terms of speed my algorithm is not as fast as sieve of Eratosthenes for large numbers. But then again, we are not talking about large numbers here. The problem asks for the 10001st prime and the algorithm is sufficient for that.

There are segmented versions of Eratosthenes that use much less memory

Again, overkill if you actually implement this for a relatively trivial problem like this.