// Arup Guha
// 2/3/2024
// Some Math Code for Junior Knights

import java.util.*;

public class math {

	public static void main(String[] args) {
		
		// Test GCD.
		System.out.println(gcd(52, 12));
		System.out.println(gcd(117, 52));
		
		// Test prime test.
		long sT = System.currentTimeMillis();
		boolean isP = isPrime(1000000007);
		long eT = System.currentTimeMillis();
		System.out.println(isP+" took "+(eT-sT)+" ms.");
	
		// Test prime sieve.
		long sT = System.currentTimeMillis();
		ArrayList<Integer> res = pList(60000000);
		long eT = System.currentTimeMillis();
		System.out.println("took "+(eT-sT)+" ms. "+res.size());
		
		// Cumulative frequency.
		int[] arr = {3,6,2,8,1,7,9,10};
		int[] cf = makeCF(arr);
		for (int i=0; i<cf.length; i++)
			System.out.print(cf[i]+" ");
		System.out.println();
		
		// MCSS.
		int[] arr2 = {3, 5, -2, 4, -3, 1, -11, 3, 2, -1, 5, 13, -2, -3, 1, 2};
		System.out.println(mcss(arr2));
	}

	// Returns the greatest common divisor of a and b.
	public static int gcd(int a, int b) {
		return b == 0 ? a : gcd(b, a%b);
	}
	
	// Returns the least common multiple of a and b.
	public static int lcm(int a, int b) {
		return a/gcd(a,b)*b;
	}
	
	// Returns true iff n is prime.
	public static boolean isPrime(int n) {
		
		// We can stop at the square root...we avoid ints.
		for (int i=2; i*i<=n; i++)
			
			// Not prime...
			if (n%i == 0)
				return false;
			
		// We are good if we get here.
		return true;
	}
	
	// Returns a list of all primes upto n.
	public static ArrayList<Integer> pList(int n) {
		
		// Assume everything is prime at first.
		boolean[] isP = new boolean[n+1];
		Arrays.fill(isP, true);
		
		// Go through each number.
		for (int i=2; i*i<=n; i++)
			
			// Cross off multiples of i. (2i, 3i, etc.)
			for (int j=2*i; j<=n; j+=i)
				isP[j] = false;
			
		// Copy over all primes into list.
		ArrayList<Integer> list = new ArrayList<Integer>();
		for (int i=2; i<=n; i++)
			if (isP[i])
				list.add(i);
			
		return list;
	}
	
	// Returns the cumulative frequency array for array.
	public static int[] makeCF(int[] array) {
		
		// Store here.
		int[] cf = new int[array.length+1];
		
		// Just add this value to the previous total.
		for (int i=1; i<cf.length; i++)
			cf[i] = cf[i-1] + array[i-1];
		
		// Ta da!
		return cf;
		
	}
	
	// Returns the MCSS of arr (must have at least 1 element.)
	public static int mcss(int[] arr) {
		
		// Store the result in res, cursum in curS.
		int res = arr[0], curS = 0;
		
		// Go through the numbers.
		for (int i=0; i<arr.length; i++) {
			
			// Add this one.
			curS += arr[i];
			
			// Update the best, if necessary.
			res = Math.max(res, curS);
			
			// Cut off the negative prefix.
			if (curS < 0)
				curS = 0;
		}
		
		return res;
	}
	
}