Lonely Numbers (Codeforces 1424J)
Tags: Math, math

In number world, two different numbers are friends if they have a lot in common, but also each one has unique perks.More precisely, two different numbers $$$a$$$ and $$$b$$$ are friends if $$$gcd(a,b)$$$, $$$\frac{a}{gcd(a,b)}$$$, $$$\frac{b}{gcd(a,b)}$$$ can form sides of a triangle.Three numbers $$$a$$$, $$$b$$$ and $$$c$$$ can form sides of a triangle if $$$a + b > c$$$, $$$b + c > a$$$ and $$$c + a > b$$$.In a group of numbers, a number is lonely if it doesn't have any friends in that group.Given a group of numbers containing all numbers from $$$1, 2, 3, ..., n$$$, how many numbers in that group are lonely?

Input: The first line contains a single integer $$$t$$$ $$$(1 \leq t \leq 10^6)$$$ - number of test cases.On next line there are $$$t$$$ numbers, $$$n_i$$$ $$$(1 \leq n_i \leq 10^6)$$$ - meaning that in case $$$i$$$ you should solve for numbers $$$1, 2, 3, ..., n_i$$$.

Output: For each test case, print the answer on separate lines: number of lonely numbers in group $$$1, 2, 3, ..., n_i$$$.

Note: For first test case, $$$1$$$ is the only number and therefore lonely.For second test case where $$$n=5$$$, numbers $$$1$$$, $$$3$$$ and $$$5$$$ are lonely.For third test case where $$$n=10$$$, numbers $$$1$$$, $$$5$$$ and $$$7$$$ are lonely.

Sample Inputs:
3
1 5 10

Sample Outputs:
1
3
3

Solution (Python):
""""""
import sys, math, cmath, time
start_time = time.time()

def seive(n):
    a = [1]
    prime = [True for i in range(n + 1)]
    p = 2
    while p * p <= n:
        if prime[p] == True:
            for i in range(p ** 2, n + 1, p):
                prime[i] = False
        p = p + 1
    for p in range(2, n + 1):
        if prime[p]:
            a.append(p)
    return a

def solve():
    q = seive(10 ** 6)
    w = [0] * 10 ** 6
    w[0] = 1
    j = 1
    qw = 0
    for i in range(1, 10 ** 6):
        if qw == 1 or q[j] > i + 1:
            w[i] = w[i - 1]
        else:
            w[i] = w[i - 1] + 1
            j = j + 1
        if j > len(q) - 1:
            j = len(q) - 1
            qw = 1
    qq = [0] * 10 ** 6
    qq[0] = 4
    qqqq = 1
    while qq[qqqq - 1] <= 10 ** 6:
        qq[qqqq] = q[qqqq + 1] ** 2
        qqqq = qqqq + 1
    qqqq = qq.index(0)
    ww = [0] * 10 ** 6
    ww[3] = 1
    j = 1
    qw = 0
    for i in range(4, 10 ** 6):
        if qw == 1 or qq[j] > i + 1:
            ww[i] = ww[i - 1]
        else:
            ww[i] = ww[i - 1] + 1
            j = j + 1
        if j > qqqq - 1:
            j = qqqq - 1
            qw = 1
    a = inlt()
    for i in range(len(a)):
        sys.stdout.write(str(w[a[i] - 1] - ww[a[i] - 1]) + ' ')

def main():
    global tt
    if not ONLINE_JUDGE:
        sys.stdin = open('input.txt', 'r')
        sys.stdout = open('output.txt', 'w')
    t = 1
    t = inp()
    t = 1
    for tt in range(1, t + 1):
        solve()
    if not ONLINE_JUDGE:
        print('Time Elapsed :', time.time() - start_time, 'seconds')
        sys.stdout.close()

def inp():
    return int(input())

def inlt():
    return list(map(int, input().split()))

def insr():
    return input().strip()

def invr():
    return map(int, input().split())

def counter(a):
    q = [0] * max(a)
    for i in range(len(a)):
        q[a[i] - 1] = q[a[i] - 1] + 1
    return q

def counter_elements(a):
    q = dict()
    for i in range(len(a)):
        if a[i] not in q:
            q[a[i]] = 0
        q[a[i]] = q[a[i]] + 1
    return q

def string_counter(a):
    q = [0] * 26
    for i in range(len(a)):
        q[ord(a[i]) - 97] = q[ord(a[i]) - 97] + 1
    return q

def factorial(n, m=1000000007):
    q = 1
    for i in range(n):
        q = q * (i + 1) % m
    return q

def factors(n):
    q = []
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            q.append(i)
            q.append(n // i)
    return list(sorted(list(set(q))))

def prime_factors(n):
    q = []
    while n % 2 == 0:
        q.append(2)
        n = n // 2
    for i in range(3, int(n ** 0.5) + 1, 2):
        while n % i == 0:
            q.append(i)
            n = n // i
    if n > 2:
        q.append(n)
    return list(sorted(q))

def transpose(a):
    (n, m) = (len(a), len(a[0]))
    b = [[0] * n for i in range(m)]
    for i in range(m):
        for j in range(n):
            b[i][j] = a[j][i]
    return b

def power_two(x):
    return x and (not x & x - 1)

def ceil(a, b):
    return -(-a // b)
ONLINE_JUDGE = __debug__
if ONLINE_JUDGE:
    import io, os
    input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
main()

Solution (Python):
""""""
import sys, math, cmath, time, collections
start_time = time.time()

def seive(n):
    a = [1]
    prime = [True for i in range(n + 1)]
    p = 2
    while p * p <= n:
        if prime[p] == True:
            for i in range(p ** 2, n + 1, p):
                prime[i] = False
        p = p + 1
    for p in range(2, n + 1):
        if prime[p]:
            a.append(p)
    return a

def solve():
    q = seive(10 ** 6)
    w = [0] * 10 ** 6
    w[0] = 1
    j = 1
    qw = 0
    for i in range(1, 10 ** 6):
        if qw == 1 or q[j] > i + 1:
            w[i] = w[i - 1]
        else:
            w[i] = w[i - 1] + 1
            j = j + 1
        if j > len(q) - 1:
            j = len(q) - 1
            qw = 1
    qq = [0] * 10 ** 6
    qq[0] = 4
    qqqq = 1
    while qq[qqqq - 1] <= 10 ** 6:
        qq[qqqq] = q[qqqq + 1] ** 2
        qqqq = qqqq + 1
    qqqq = qq.index(0)
    ww = [0] * 10 ** 6
    ww[3] = 1
    j = 1
    qw = 0
    for i in range(4, 10 ** 6):
        if qw == 1 or qq[j] > i + 1:
            ww[i] = ww[i - 1]
        else:
            ww[i] = ww[i - 1] + 1
            j = j + 1
        if j > qqqq - 1:
            j = qqqq - 1
            qw = 1
    a = inlt()
    for i in range(len(a)):
        sys.stdout.write(str(w[a[i] - 1] - ww[a[i] - 1]) + ' ')

def main():
    global tt
    if not ONLINE_JUDGE:
        sys.stdin = open('input.txt', 'r')
        sys.stdout = open('output.txt', 'w')
    t = 1
    t = inp()
    t = 1
    for tt in range(1, t + 1):
        solve()
    if not ONLINE_JUDGE:
        print('Time Elapsed :', time.time() - start_time, 'seconds')
        sys.stdout.close()

def inp():
    return int(input())

def inlt():
    return list(map(int, input().split()))

def insr():
    return input().strip()

def invr():
    return map(int, input().split())

def counter(a):
    q = [0] * max(a)
    for i in range(len(a)):
        q[a[i] - 1] = q[a[i] - 1] + 1
    return q

def counter_elements(a):
    q = dict()
    for i in range(len(a)):
        if a[i] not in q:
            q[a[i]] = 0
        q[a[i]] = q[a[i]] + 1
    return q

def string_counter(a):
    q = [0] * 26
    for i in range(len(a)):
        q[ord(a[i]) - 97] = q[ord(a[i]) - 97] + 1
    return q

def factorial(n, m=1000000007):
    q = 1
    for i in range(n):
        q = q * (i + 1) % m
    return q

def factors(n):
    q = []
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            q.append(i)
            q.append(n // i)
    return list(sorted(list(set(q))))

def prime_factors(n):
    q = []
    while n % 2 == 0:
        q.append(2)
        n = n // 2
    for i in range(3, int(n ** 0.5) + 1, 2):
        while n % i == 0:
            q.append(i)
            n = n // i
    if n > 2:
        q.append(n)
    return list(sorted(q))

def transpose(a):
    (n, m) = (len(a), len(a[0]))
    b = [[0] * n for i in range(m)]
    for i in range(m):
        for j in range(n):
            b[i][j] = a[j][i]
    return b

def power_two(x):
    return x and (not x & x - 1)

def ceil(a, b):
    return -(-a // b)
ONLINE_JUDGE = __debug__
if ONLINE_JUDGE:
    import io, os
    input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
main()

Solution (Python):
""""""
import sys, math, cmath, time, collections
start_time = time.time()

def seive(n):
    a = [1]
    prime = [True for i in range(n + 1)]
    p = 2
    while p * p <= n:
        if prime[p] == True:
            for i in range(p ** 2, n + 1, p):
                prime[i] = False
        p = p + 1
    for p in range(2, n + 1):
        if prime[p]:
            a.append(p)
    return a

def solve():
    q = seive(10 ** 6)
    w = [0] * 10 ** 6
    w[0] = 1
    j = 1
    qw = 0
    for i in range(1, 10 ** 6):
        if qw == 1 or q[j] > i + 1:
            w[i] = w[i - 1]
        else:
            w[i] = w[i - 1] + 1
            j = j + 1
        if j > len(q) - 1:
            j = len(q) - 1
            qw = 1
    qq = [0] * 10 ** 6
    qq[0] = 4
    qqqq = 1
    while qq[qqqq - 1] <= 10 ** 6:
        qq[qqqq] = q[qqqq + 1] ** 2
        qqqq = qqqq + 1
    qqqq = qq.index(0)
    ww = [0] * 10 ** 6
    ww[3] = 1
    j = 1
    qw = 0
    for i in range(4, 10 ** 6):
        if qw == 1 or qq[j] > i + 1:
            ww[i] = ww[i - 1]
        else:
            ww[i] = ww[i - 1] + 1
            j = j + 1
        if j > qqqq - 1:
            j = qqqq - 1
            qw = 1
    a = inlt()
    for i in range(len(a)):
        sys.stdout.write(str(w[a[i] - 1] - ww[a[i] - 1]) + ' ')

def main():
    global tt
    if not ONLINE_JUDGE:
        sys.stdin = open('input.txt', 'r')
        sys.stdout = open('output.txt', 'w')
    t = 1
    t = inp()
    t = 1
    for tt in range(1, t + 1):
        solve()
    if not ONLINE_JUDGE:
        print('Time Elapsed :', time.time() - start_time, 'seconds')
        sys.stdout.close()

def inp():
    return int(input())

def inlt():
    return list(map(int, input().split()))

def insr():
    return input().strip()

def invr():
    return map(int, input().split())

def counter(a):
    q = [0] * max(a)
    for i in range(len(a)):
        q[a[i] - 1] = q[a[i] - 1] + 1
    return q

def counter_elements(a):
    q = dict()
    for i in range(len(a)):
        if a[i] not in q:
            q[a[i]] = 0
        q[a[i]] = q[a[i]] + 1
    return q

def string_counter(a):
    q = [0] * 26
    for i in range(len(a)):
        q[ord(a[i]) - 97] = q[ord(a[i]) - 97] + 1
    return q

def factorial(n, m=1000000007):
    q = 1
    for i in range(n):
        q = q * (i + 1) % m
    return q

def factors(n):
    q = []
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            q.append(i)
            q.append(n // i)
    return list(sorted(list(set(q))))

def prime_factors(n):
    q = []
    while n % 2 == 0:
        q.append(2)
        n = n // 2
    for i in range(3, int(n ** 0.5) + 1, 2):
        while n % i == 0:
            q.append(i)
            n = n // i
    if n > 2:
        q.append(n)
    return list(sorted(q))

def transpose(a):
    (n, m) = (len(a), len(a[0]))
    b = [[0] * n for i in range(m)]
    for i in range(m):
        for j in range(n):
            b[i][j] = a[j][i]
    return b

def power_two(x):
    return x and (not x & x - 1)

def ceil(a, b):
    return -(-a // b)
ONLINE_JUDGE = __debug__
if ONLINE_JUDGE:
    import io, os
    input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
main()