Project Euler/58
From charlesreid1
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 project euler notes
Round 1: Problems 1-20 Problem 1 · Problem 2 · Problem 3 · Problem 4 · Problem 5 · Problem 6 · Problem 7 · Problem 8 · Problem 9 · Problem 10 Problem 11 · Problem 12 · Problem 13 · Problem 14 · Problem 15 · Problem 16 · Problem 17 · Problem 18 · Problem 19 · Problem 20 Round 2: Problems 50-70 Problem 51 · Problem 52 · Problem 53 · Problem 54 · Problem 55 · Problem 56 · Problem 57 · Problem 58 · ... · Problem 61 · Problem 62 · Problem 63 · Problem 64 · Problem 65 · Problem 66 · Problem 67 Round 3: Problems 100-110 Problem 100 · Problem 101 · Problem 102 Round 4: Problems 500-510 Problem 500 · Problem 501 * · Problem 502 * Round 5: Problems 150-160 Round 6: Problems 250-260 Round 7: Problems 170-180
|