import multiprocessing
from multiprocessing import Manager, Process

def prime_divs(right_border):
    divs_limit = int(right_border**0.5)
    div_is_prime = [True] * (divs_limit + 1)
    divs = []

    for p in range(2, divs_limit + 1):
        if div_is_prime[p]:
           divs.append(p)
           for i in range(p * p, divs_limit + 1, p):
               div_is_prime[i] = False

    return divs

def count_segmented(
                    low_limit,
                    high_limit,
                    global_left,
                    global_right,
                    divs,
                    shared_array,
                    index
                   ):

    if low_limit > high_limit:
        shared_array[index] = 0
        return 0

    segment_len = high_limit - low_limit + 1
    segment_is_prime = [True] * segment_len

    for p in divs:
        start_num = ((low_limit + p - 1) // p) * p

        if start_num < p * p:
            start_num = p * p
        
        start_idx = start_num - low_limit

        if start_idx < segment_len:
            for idx in range(start_idx, segment_len, p):
                segment_is_prime[idx] = False

    results = []
    count = 0
    for i in range(segment_len):
        if segment_is_prime[i]:
            p = low_limit + i
            if p < 2: 
                continue
            val = p**4
            if val >= global_left and val <= global_right:
                results.append(val)
                count += 1

    shared_array[index] = results



def main():
    num_of_threads = multiprocessing.cpu_count()
    N = 10**37
    # N = 10**11
    # global_left_border = 10**10
    global_left_border = 10*1

    root_limit = int(N**0.25)

    divs = prime_divs(root_limit);

    if root_limit < num_of_threads:
        segment_size = 1
        real_threads = root_limit // 1
    else:
        segment_size = root_limit // num_of_threads
        real_threads = num_of_threads

    with Manager() as manager:
        results = manager.dict()

        current_low = 2
        processes = []

        for thrd in range(real_threads):
            if thrd == real_threads- 1:
                current_high = root_limit
            else:
                current_high = current_low + segment_size - 1

            p = Process(target=count_segmented, args=(current_low, current_high, global_left_border, N, divs, results, thrd))
            processes.append(p)
            current_low = current_high + 1

        for p in processes:
            p.start()

        for p in processes:
            p.join()

        count = 0
        for num_list in results.values():
            # print(num_list)
            count += len(num_list)
        print(count)

if __name__ == "__main__":
    main()