import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

public class PrimeConsec {

	public static int consecKprimes (int k, long[] arr) {
		int counter = 0;

		for (int i = 1; i < arr.length; i++) {
			long larger = Math.max(arr[i], arr[i - 1]);
			long smaller = Math.min(arr[i], arr[i - 1]);

			List<Long> kPrimes = generateKPrimes(k, smaller, larger);

			if (kPrimes.contains(smaller) && kPrimes.contains(larger)) counter++;
		}

		return counter;
	}

	public static List<Long> generateKPrimes (int k, long start, long end) {
		List<Long> result = new ArrayList<>();

		for (long i = start == 0 ? 2 : start; i <= end; i++) {
			int numOfFactors = 0;
			long cur = i;

			for (int j = 2; j <= cur / j; j++) {
				while (cur % j == 0) {
					numOfFactors++;
					cur /= j;
				}
			}
			if (cur > 1) numOfFactors++;

			if (numOfFactors == k) result.add(i);
		}

		return result;
	}
}