# Difference between revisions of "Project Euler/58"

### From charlesreid1

(→Problem Statement) |
m (Replacing charlesreid1.com:3000 with git.charlesreid1.com) |
||

Line 50: | Line 50: | ||

</pre> | </pre> | ||

− | Link: https://charlesreid1.com | + | Link: https://git.charlesreid1.com/cs/euler/src/master/scratch/Round2_050-070/058/Problem058.java |

==Flags== | ==Flags== | ||

{{ProjectEulerFlag}} | {{ProjectEulerFlag}} |

## Latest revision as of 03:48, 9 October 2019

## 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 **both 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://git.charlesreid1.com/cs/euler/src/master/scratch/Round2_050-070/058/Problem058.java

## Flags

Project Euler
Problem 1
Problem 11
Problem 51
Problem 100
Problem 500
- = in progress
· Template:ProjectEulerFlag · e |