Solution to Project Euler Problem 58: Spiral primes - Starting with 1 and spiralling anticlockwise in the following way, a square spiral with side length 7 is formed. It is interesting to note that the odd squares lie along the bottom right diagonal, but what is more interesting is that 8 out of the 13 numbers lying along both diagonals are prime; that is, a ratio of 8/13 ≈ 62%. If one complete new layer is wrapped around the spiral above, a square spiral with side length 9 will be formed. If this process is continued, what is the side length of the square spiral for which the ratio of primes along both diagonals first falls below 10%?

• Java Code

package sikademy;
/**
 *
 * @author Archangel Macsika
 * Copyright (c) Sikademy. All rights reserved
 */

public class SikademyEulerSolution {
	
	public String run() {
		int numPrimes = 0;
		for (int n = 1; ; n += 2) {
			for (int i = 0; i < 4; i++) {
				if (Library.isPrime(n * n - i * (n - 1)))
					numPrimes++;
			}
			if (n > 1 && numPrimes * 10 < n * 2 - 1)
				return Integer.toString(n);
		}
		
	}

        public static boolean isPrime(int x) {
		if (x < 0)
			throw new IllegalArgumentException("Negative number");
		if (x == 0 || x == 1)
			return false;
		else if (x == 2)
			return true;
		else {
			if (x % 2 == 0)
				return false;
			for (int i = 3, end = sqrt(x); i <= end; i += 2) {
				if (x % i == 0)
					return false;
			}
			return true;
		}
	}

        public static int sqrt(int x) {
		if (x < 0)
			throw new IllegalArgumentException("Square root of negative number");
		int y = 0;
		for (int i = 1 << 15; i != 0; i >>>= 1) {
			y |= i;
			if (y > 46340 || y * y > x)
				y ^= i;
		}
		return y;
	}


	public static void main(String[] args) {
                SikademyEulerSolution solution = new SikademyEulerSolution();
		System.out.println(solution.run());
	}	
}

• Python Code

# 
# @author Archangel Macsika
# Copyright (c) Sikademy. All rights reserved.
# 

import fractions, itertools



def compute():
	TARGET = fractions.Fraction(1, 10)
	numprimes = 0
	for n in itertools.count(1, 2):
		for i in range(4):
			if is_prime(n * n - i * (n - 1)):
				numprimes += 1
		if n > 1 and fractions.Fraction(numprimes, n * 2 - 1) < TARGET:
			return str(n)

def is_prime(x):
	if x <= 1:
		return False
	elif x <= 3:
		return True
	elif x % 2 == 0:
		return False
	else:
		for i in range(3, sqrt(x) + 1, 2):
			if x % i == 0:
				return False
		return True

def sqrt(x):
	assert x >= 0
	i = 1
	while i * i <= x:
		i *= 2
	y = 0
	while i > 0:
		if (y + i)**2 <= x:
			y += i
		i //= 2
	return y

if __name__ == "__main__":
	print(compute())