QUIZ_4

## Written by *** for COMP9021

# Implements a function that computes the maximum
# number of primes within a window of a given size,
# the first of which starts from a given lower bound
# and the last of which ends at a given upper bound.
# For all windows that achieve that maximum number
# within the window; outputs those two primes
# from smallest to largest first primes.
import timeit
from math import sqrt
from collections import deque
from collections import defaultdict


def sieve_of_primes_up_to(n):
    sieve = [True] * (n + 1)
    for p in range(2, round(sqrt(n)) + 1):
        if sieve[p]:
            for i in range(p * p, n + 1, p):
                sieve[i] = False
    return sieve


# You can assume that the function will be called with
# size a strictly positive integer,
# lower_bound an integer at least equal to 2, and
# upper_bound an integer at least equal to lower_bound.
# The function won't be tested for values of upper_bound
# greater than 10,000,000.

def primes_in_window(size, lower_bound, upper_bound):
    if size > upper_bound - lower_bound + 1:
        print('Window size is too large for these bounds,',
              'leaving it there.'
              )
        return

    dict_length = defaultdict(list)
    # starttime = timeit.default_timer()
    dq_window = deque()
    prime_list = sieve_of_primes_up_to(upper_bound)
    cur_number = 1
    while cur_number < len(prime_list):
        if cur_number >= lower_bound:
            if dq_window and cur_number - dq_window[0] >= size:
                dq_window.popleft()
            if prime_list[cur_number]:
                dq_window.append(cur_number)
                length_of_window = len(dq_window)
                dict_length[length_of_window].append([dq_window[0], dq_window[-1]])

        cur_number += 1
    if dict_length:
        max_length = max(dict_length.keys())
    else:
        print(f'There is no prime in a window of size {size}.')
        return
    # print('dict_length',dict_length)
    # print(max_length)
    if max_length == 1:
        print(f'There is at most one prime in a window of size {size}.')
    elif max_length > 1:
        print(f'There are at most {max_length} primes in a window of size {size}.')
    for value in dict_length[max_length]:
        # print(value[0], value[1])
        print(f'In some window, the smallest prime is {value[0]} and the largest one is {value[1]}.')
    # print(max_length)
    # print("The time difference is :", timeit.default_timer() - starttime)

# 4 2 7 5:7
# 7 10 30 23:29

# return filtered_dict
# primes_in_window(10000, 1000, 10000000)