import threading

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,
                    result_list,
                    index
                   ):

    if low_limit > high_limit:
        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

    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:
                result_list.append(val)
                count += 1

    # print(count)
    # return count



def main():
    num_of_threads = 16
    N = 10**30
    # 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

    current_low = 2
    threads = []
    results = [[] for _ in range(real_threads)]

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

        t = threading.Thread(target=count_segmented, args=(current_low, current_high, global_left_border, N, divs, results[thrd], thrd))
        threads.append(t)
        current_low = current_high + 1

    for t in threads:
        t.start()

    for t in threads:
        t.join()

    count = 0
    for thrd in results:
        # for i in thrd:
        #     print(i)
        count += len(thrd)
    print(count)

if __name__ == "__main__":
    main()