Lonely Numbers (Codeforces 1423K)
Tags: Math, two pointers

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 os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def RL():
    return map(int, sys.stdin.readline().rstrip().split())

def RLL():
    return list(map(int, sys.stdin.readline().rstrip().split()))

def N():
    return int(input())

def print_list(l):
    print(' '.join(map(str, l)))
from math import ceil, floor, sqrt, pow

def judgePrime(n):
    if n < 2:
        return []
    else:
        output = [1] * n
        (output[0], output[1]) = (0, 0)
        for i in range(2, int(n ** 0.5) + 1):
            if output[i] == 1:
                output[i * i:n:i] = [0] * len(output[i * i:n:i])
    return output
prime = judgePrime(1000005)
s = [0]
for i in range(1, 1000005):
    s.append(s[-1] + prime[i])
t = N()
a = RL()
for n in a:
    print(s[n] - s[int(sqrt(n))] + 1)

Solution (Python):
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def RL():
    return map(int, sys.stdin.readline().rstrip().split())

def RLL():
    return list(map(int, sys.stdin.readline().rstrip().split()))

def N():
    return int(input())

def print_list(l):
    print(' '.join(map(str, l)))
from math import ceil, floor, sqrt, pow

def judgePrime(n):
    if n < 2:
        return []
    else:
        output = [1] * n
        (output[0], output[1]) = (0, 0)
        for i in range(2, int(n ** 0.5) + 1):
            if output[i] == 1:
                output[i * i:n:i] = [0] * len(output[i * i:n:i])
    return output
prime = judgePrime(1000005)
s = [0]
for i in range(1, 1000005):
    s.append(s[-1] + prime[i])
t = N()
a = RL()
for n in a:
    print(s[n] - s[int(sqrt(n))] + 1)

Solution (Python):
import os, sys
from io import BytesIO, IOBase

def main():
    sieve = [0] * (10 ** 6 + 1)
    primes = [0] * (10 ** 6 + 1)
    for i in range(2, 10 ** 6 + 1):
        if not sieve[i]:
            primes[i] += 1
            if i * i <= 10 ** 6:
                primes[i * i] -= 1
            for x in range(i * i, 10 ** 6 + 1, i):
                sieve[x] = 1
    primes[1] = 1
    for i in range(1, 10 ** 6 + 1):
        primes[i] += primes[i - 1]
    _ = input()
    for i in map(int, input().split()):
        print(primes[i])
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
if __name__ == '__main__':
    main()