Project Euler/58

Problem Statement

This question asks about prime spirals.

If we form a spiral with the integers, we find that prime numbers tend to fall on the diagonals of this spiral with a higher density than elsewhere in the spiral. This question asks to find how long it takes before the percentage of integers on the diagonals that are primes falls below 10%.

Link: https://projecteuler.net/problem=58

Solution Technique

Finding the numbers that lie on the diagonals of the spiral consists of iterating through a vector of integers at intervals of increasing spacing. So all we need to do is implement a counter to generate integers, a variable to keep track of how many integers until the next number on the diagonal, and a method to check if a number is prime.

Code

Here is the core of the method, which uses a queue to pop two numbers (east/west) at a time:

		while(!q.isEmpty()) {

			// Remove two diagonals (one row) at a time
			// (problem asks for ratio of primes on *both* diagonals)
			ned = q.remove(); numbers++;
			nwd = q.remove(); numbers++;
			row++;

			if(Sieve.isPrime(ned)) {
				primes++;
			}
			if(Sieve.isPrime(nwd)) {
				primes++;
			}

			// Update ratio
			ratio = (1.0*primes)/numbers;

			if(row%1000==0) { 
				System.out.println(row);
			}

			// If < 10%, return
			if(ratio <= 0.10) { 
				return Integer.toString(row+1);
			}

			// If not < 10%, increment i and compute next entries
			q.add(nextNE(ned,row+1));
			q.add(nextNW(nwd,row+1));

		}

Link: https://charlesreid1.com:3000/cs/euler/src/master/scratch/Round2_050-070/058/Problem058.java