(Java) Project Euler 027 - Quadratic Primes

// Euler discovered the remarkable quadratic formula:

// n^2 + n + 41

// It turns out that the formula will produce 40 primes for the consecutive integer values 0 <= n <= 39.
// However, when n = 40, 40^2 + 40 + 41 = 40(40+1) + 41 is divisible by 41,
// and certainly when n = 41, 41^2 + 41 + 41 is clearly divisible by 41.

// The incredible formula n^2 - 79n + 1601 was discovered,
// which produces 80 primes for the consecutive values 0 <= n <= 79.
// The product of the coefficients, -79 and 1601, is -126479.

// Considering quadratics of the form:

// n^2 + an + b, where |a| < 1000 and |b| <= 1000

// where |n| is the modulus/absolute value of n
// e.g. |11| = 11 and |-4| = 4

// Find the product of the coefficients, a and b,
// for the quadratic expression that produces the maximum number of primes for consecutive values of n, starting with n = 0.​

 

public class ProjectEuler_027 {
    public static void main(String[] args) {
        // 초기값 설정
        int maxPrimes = 0;
        int result = 0;

        // 계수 a에 대한 외부 루프
        for (int a = -999; a < 1000; a++) {
            // 계수 b에 대한 내부 루프
            for (int b = -1000; b <= 1000; b++) {
                // 현재 계수 a, b에 대한 연속 소수 개수 계산
                int consecutivePrimes = countConsecutivePrimes(a, b);

                // 최대 연속 소수 개수 업데이트
                if (consecutivePrimes > maxPrimes) {
                    maxPrimes = consecutivePrimes;
                    result = a * b;
                }
            }
        }

        // 결과 출력
        System.out.println("Product of coefficients (a * b): " + result);
    }

    // 연속 소수 개수 계산
    static int countConsecutivePrimes(int a, int b) {
        int n = 0;

        // n에 대한 연속 소수인지 확인
        while (isPrime(quadraticFormula(n, a, b))) {
            n++;
        }

        return n;
    }

    // 이차 방정식 계산
    static int quadraticFormula(int n, int a, int b) {
        return n * n + a * n + b;
    }

    // 소수인지 확인
    static boolean isPrime(int num) {
        // 2 미만의 숫자는 소수가 아님
        if (num < 2) {
            return false;
        }

        // 2부터 제곱근까지의 수로 나누어 떨어지면 소수가 아님
        for (int i = 2; i <= Math.sqrt(num); i++) {
            if (num % i == 0) {
                return false;
            }
        }

        return true;
    }
}