Recently, Greg got a grid with n rows and m columns. Rows are indexed from 1 to n and columns are indexed from 1 to m. The cell $ ( i , j )$ is the cell of intersection of row i and column j. Each cell has a number written on it. The number written on cell  $( i , j )$  is equal to  $(i+j)$.  
Now, Greg wants to select some cells from the grid, such that for every pair of  selected cells ,the numbers on the cells are co-prime.  Determine the maximum number of cells that Greg can select.

------ Input  ------ 

Single line containing  integers n and m denoting number of rows and number of columns respectively.

------ Output ------ 

Single line containing the answer.

------ Constraints ------ 

$$1 ≤ n,m ≤ 10^{6}$$

----- Sample Input 1 ------ 
3 4

----- Sample Output 1 ------ 
4

Source: codechef | Difficulty: MEDIUM
Tags: Number theory

Mathematics


Solutions:
l = [True] * 2000001
for i in range(2, 2000001):
	if l[i]:
		for j in range(2 * i, 2000000, i):
			l[j] = False
	if i * i > 2000000:
		break
mark = 0
for i in range(2, 2000001):
	if l[i]:
		mark += 1
	l[i] = mark
(n, m) = map(int, input().split())
res = l[n + m]
print(res)


MAXN = 2000003
seive = [True] * MAXN
seive[1] = False
count = [0] * MAXN
for i in range(2, MAXN):
	if seive[i]:
		for j in range(i * i, MAXN, i):
			seive[j] = False
	if i * i > MAXN:
		break
current = 0
for i in range(2, MAXN):
	if seive[i]:
		current += 1
	count[i] = current
(n, m) = map(int, input().split())
print(count[n + m])


prime_factors = [i for i in range(2 * 10 ** 6 + 1)]
prime_arr = []
count = 0
for i in range(2, 2 * 10 ** 6 + 1):
	if prime_factors[i] == i:
		prime_arr.append(i)
		num = i * i
		count += 1
		while num <= 2 * 10 ** 6:
			if prime_factors[num] == num:
				prime_factors[num] = i
			num += i
prime_arr_len = len(prime_arr)

def bin_search_primes(num):
	start = 0
	end = prime_arr_len - 1
	while start <= end:
		middle = (start + end) // 2
		if prime_arr[middle] == num or (prime_arr[middle] < num and (middle + 1 == prime_arr_len or prime_arr[middle + 1] > num)):
			return middle + 1
		elif prime_arr[middle] > num:
			end = middle - 1
		else:
			start = middle + 1
(rows, columns) = map(int, input().split())
print(bin_search_primes(rows + columns))


def sieve(n):
	prime = [i for i in range(n + 1)]
	prime[0] = True
	prime[1] = True
	p = 2
	while p * p <= n:
		if prime[p] != True:
			for i in range(p * p, n + 1, p):
				prime[i] = True
		p += 1
	prime = list(set(prime))
	del prime[0]
	return prime
(n, m) = map(int, input().split())
print(len(sieve(n + m)))


def sieve(n):
	prime = [True for i in range(n + 1)]
	prime[0] = True
	prime[1] = True
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	num = 0
	for i in range(2, n + 1):
		if prime[i]:
			num += 1
	return num
(n, m) = map(int, input().split())
print(sieve(n + m))


try:
	ans = []

	def SieveOfEratosthenes(n):
		prime = [True for i in range(n + 1)]
		p = 2
		while p * p <= n:
			if prime[p] == True:
				for i in range(p * p, n + 1, p):
					prime[i] = False
			p += 1
		for p in range(2, n + 1):
			if prime[p]:
				ans.append(p)
	(n, m) = map(int, input().split())
	SieveOfEratosthenes(n + m)
	print(len(ans))
except Exception:
	pass


(n, m) = map(int, input().split())
mi = 2
ma = n + m
ans = [1 for i in range(ma + 1)]
for i in range(2, int(ma ** 0.5) + 1):
	for j in range(i + i, ma + 1, i):
		ans[j] = 0
ans[0] = 0
ans[1] = 0
print(ans.count(1))


(n, m) = map(int, input().split())
k = 10000 * 1000 + 7
a = [1] * k
a[0] = a[1] = 0
i = 2
while i * i <= k:
	x = i * i
	if a[i] == 1:
		for j in range(x, k, i):
			a[j] = 0
	i += 1
p = 0
for i in range(2, m + n + 1):
	if a[i] == 1:
		p += 1
print(p)


def SieveOfEratosthenes(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	c = 0
	for p in range(2, n):
		if prime[p]:
			c += 1
	print(c)
from sys import stdin

def get_array():
	return [int(x) for x in stdin.readline().rstrip().split()]
arr = get_array()
SieveOfEratosthenes(arr[0] + arr[1] + 1)


def SieveOfEratosthenes(n):
	prime = [True for i in range(n + 1)]
	p = 2
	c = 0
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	for p in range(2, n):
		if prime[p]:
			c += 1
	print(c)
(r, c) = map(int, input().split())
SieveOfEratosthenes(r + c + 1)


a = input().split(' ')
n = int(a[0]) + int(a[1])
l = [1 for i in range(n + 1)]
l[0] = 0
l[1] = 0
p = 2
while p * p <= n:
	if l[p]:
		for i in range(p * p, n + 1, p):
			l[i] = 0
	p += 1
count = 0
for i in l:
	if i:
		count += 1
print(count)


def SieveOfEratosthenes(n):
	prime = [True for i in range(n + 1)]
	p = 2
	c = 0
	while p * p <= n:
		if prime[p]:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	for p in range(2, n):
		if prime[p]:
			c += 1
	print(c)
(n, m) = [int(i) for i in input().split()]
max_n = n + m + 1
SieveOfEratosthenes(max_n)


from math import *
(n, m) = map(int, input().split())
s = 0
l = [0] * (n + m + 1)
for i in range(2, n + m + 1):
	if l[i] == 0:
		for j in range(i ** 2, n + m + 1, i):
			l[j] = 1
for i in range(2, n + m + 1):
	if l[i] == 0:
		s += 1
print(s)


def isprime(n):
	if n == 1:
		return False
	if n != 2 and n % 2 == 0:
		return False
	for i in range(3, int(n ** 0.5) + 1, 2):
		if n % i == 0:
			return False
	return True
(n, m) = map(int, input().split())
primes = 0
for i in range(2, n + m + 1):
	primes += int(isprime(i))
print(primes)


def Sieve(n):
	prime = []
	c = 0
	for i in range(0, n + 2):
		prime.append(True)
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	for i in range(2, n + 1):
		if prime[i] == True:
			c += 1
	return c
(n, m) = list(map(int, input().split()))
print(Sieve(n + m))


(n, m) = map(int, input().split())
pi = []

def prime(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	for p in range(2, n):
		if prime[p]:
			pi.append(p)
	print(len(pi))
prime(n + m + 1)


def Sieve(n):
	prime = [1 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] = 0
		p += 1
	return prime
try:
	(n, m) = list(map(int, input().split()))
	x = Sieve(n + m)
	print(sum(x) - 2)
except:
	pass


import math

def sieve(n):
	l = [True] * (n + 1)
	prime = []
	start = 2
	end = int(math.sqrt(n))
	while start <= end:
		if l[start] == True:
			prime.append(start)
			for i in range(start * start, n + 1, start):
				if l[i] == True:
					l[i] = False
		start += 1
	for j in range(end + 1, n + 1):
		if l[j] == True:
			prime.append(j)
	return prime
(n, m) = map(int, input().split())
print(len(sieve(n + m)))


def prime(n):
	if n <= 1:
		return 0
	if n <= 3:
		return 1
	if n % 2 == 0 or n % 3 == 0:
		return 0
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return 0
		i = i + 6
	return 1
(n, m) = map(int, input().split())
ans = []
ans.append(2)
for i in range(3, n + m + 1, 2):
	if prime(i) == 1:
		ans.append(i)
print(len(set(ans)))


def isprime(x):
	if x == 2 or x == 3:
		return True
	elif x % 2 == 0 or x % 3 == 0:
		return False
	else:
		a = int(x ** (1 / 2))
		for i in range(5, a + 1, 6):
			if x % i == 0 or x % (i + 2) == 0:
				return False
		return True
(n, m) = map(int, input().strip().split())
lower = 2
upper = n + m
cu = 0
for i in range(lower, upper + 1):
	if isprime(i) == True:
		cu += 1
print(cu)


def sieve(n):
	prime = []
	for i in range(0, n + 1):
		prime.append(True)
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for j in range(p * p, n + 1, p):
				prime[j] = False
		p = p + 1
	prime = prime[2:]
	return prime.count(True)
(n1, m1) = map(int, input().split())
a = n1 + m1
print(sieve(a))


(m, n) = map(int, input().split())
l = [1] * (m + n + 1)
l[0] = 0
l[1] = 0
for i in range(2, int((m + n) ** 0.5) + 1):
	if l[i] == 1:
		for j in range(2 * i, m + n + 1, i):
			l[j] = 0
print(l.count(1))


import math

def isprime(n):
	F = math.floor(math.sqrt(n))
	for i in range(2, F + 1):
		if n % i == 0:
			return False
	return True
p = input().rstrip().split(' ')
a = int(p[0])
b = int(p[1])
A = 2
G = 0
B = 2 + (a - 1) + (b - 1)
l = [1] * (B + 1)
l[0] = 0
l[1] = 0
C = math.floor(math.sqrt(B))
for i in range(2, C + 1):
	if l[i] == 1 and isprime(i):
		l[i] = 1
		A = 2
		T = i * A
		while T < len(l):
			l[T] = 0
			A += 1
			T = i * A
print(l.count(1))


def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True
(x, y) = map(int, input().split())
list = []
count = 0
for i in range(x + y + 1):
	if isPrime(i):
		count += 1
print(count)


def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True

def printPrime(n):
	x = 0
	for i in range(2, n + 1):
		if isPrime(i):
			x += 1
	return x
(n, m) = input().split()
print(printPrime(int(n) + int(m)))


def get_the_number_of_primes_less_than_or_equal_to_n(n):
	is_prime = [True for i in range(n + 1)]
	is_prime[0] = False
	is_prime[1] = False
	num_of_primes = 0
	p = 2
	while p * p <= n:
		if is_prime[p] == True:
			for i in range(2 * p, n + 1, p):
				is_prime[i] = False
		p += 1
	for i in range(2, n + 1):
		if is_prime[i] == True:
			num_of_primes += 1
	return num_of_primes
(n, m) = list(map(int, input().split()))
print(get_the_number_of_primes_less_than_or_equal_to_n(n + m))


(n, m) = list(map(int, input().split()))
maxa = n + m
prime = [1 for i in range(maxa + 1)]
prime[0] = 0
prime[1] = 0
for i in range(2, maxa + 1):
	if prime[i] == 1:
		for j in range(i * i, maxa + 1, i):
			prime[j] = 0
ans = 0
for i in range(2, maxa + 1):
	if prime[i] == 1:
		ans += 1
if ans <= 1:
	print(0)
else:
	print(ans)


def SieveOfEratosthenes(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	count = 0
	for p in range(2, n + 1):
		if prime[p]:
			count = count + 1
	print(count)
(n, m) = map(int, input().split())
SieveOfEratosthenes(n + m)


import sys
from math import sqrt
sys.setrecursionlimit(10 ** 5 + 1)
inf = int(10 ** 20)
max_val = inf
min_val = -inf
RW = lambda : sys.stdin.readline().strip()
RI = lambda : int(RW())
RMI = lambda : [int(x) for x in sys.stdin.readline().strip().split()]
RWI = lambda : [x for x in sys.stdin.readline().strip().split()]

def seive(limit):
	status = [True for _ in range(limit + 1)]
	primes = []
	for i in range(2, limit + 1):
		if status[i]:
			primes.append(i)
			for j in range(i * i, limit + 1, i):
				status[j] = False
	return primes
(a, b) = RMI()
print(len(seive(a + b)))


def prime(n):
	p = [True for i in range(n + 1)]
	d = int(n ** 0.5) + 1
	for i in range(2, d + 1):
		if p[i] == True:
			for j in range(i * i, n + 1, i):
				p[j] = False
	prime = []
	for i in range(2, len(p)):
		if p[i] == True:
			prime.append(i)
	return len(prime)
s = input('').split(' ')
n = int(s[0])
m = int(s[1])
print(prime(n + m))


from math import sqrt

def prime(c):
	p = [True for i in range(c + 1)]
	d = int(sqrt(c))
	for i in range(2, d + 1):
		if p[i] == True:
			for j in range(i * i, c + 1, i):
				p[j] = False
	yo = []
	for k in range(2, c + 1):
		if p[k]:
			yo.append(k)
	return yo
(a, b) = map(int, input().split())
c = a + b
print(len(prime(c)))


def primes(n):
	prime = [True for i in range(n + 1)]
	p = 2
	prime[0] = False
	prime[1] = False
	while p * p <= n:
		if prime[p]:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	return sum(prime)
(n, m) = [int(x) for x in input().split(' ')]
a = n + m
print(primes(a))


def seive(n):
	nonprimes = (n + 1) * [False]
	count = 0
	nonprimes[0] = nonprimes[1] = True
	for i in range(2, n + 1):
		if not nonprimes[i]:
			count += 1
			for j in range(2 * i, n + 1, i):
				nonprimes[j] = True
	print(count)
(r, c) = map(int, input().split())
k = r + c
seive(k)


prime = [True for x in range(2000001)]
for i in range(2, 2001):
	if prime[i]:
		for j in range(i * i, 2000001, i):
			prime[j] = False
(n, m) = map(int, input().split())
count = 0
for i in range(2, n + m + 1):
	if prime[i]:
		count += 1
print(count)


def primes235(limit):
	yield 2
	yield 3
	yield 5
	if limit < 7:
		return
	modPrms = [7, 11, 13, 17, 19, 23, 29, 31]
	gaps = [4, 2, 4, 2, 4, 6, 2, 6, 4, 2, 4, 2, 4, 6, 2, 6]
	ndxs = [0, 0, 0, 0, 1, 1, 2, 2, 2, 2, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 6, 6, 7, 7, 7, 7, 7, 7]
	lmtbf = (limit + 23) // 30 * 8 - 1
	lmtsqrt = int(limit ** 0.5) - 7
	lmtsqrt = lmtsqrt // 30 * 8 + ndxs[lmtsqrt % 30]
	buf = [True] * (lmtbf + 1)
	for i in range(lmtsqrt + 1):
		if buf[i]:
			ci = i & 7
			p = 30 * (i >> 3) + modPrms[ci]
			s = p * p - 7
			p8 = p << 3
			for j in range(8):
				c = s // 30 * 8 + ndxs[s % 30]
				buf[c::p8] = [False] * ((lmtbf - c) // p8 + 1)
				s += p * gaps[ci]
				ci += 1
	for i in range(lmtbf - 6 + ndxs[(limit - 7) % 30]):
		if buf[i]:
			yield (30 * (i >> 3) + modPrms[i & 7])
from itertools import takewhile
(n, m) = map(int, input().split())
print(len(list(takewhile(lambda x: x <= m + n, primes235(m + n)))))


def primes(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	c = 0
	for p in range(2, n):
		if prime[p]:
			c += 1
	print(c)
(a, b) = map(int, input().split())
primes(a + b + 1)


(num, m) = map(int, input().split())
count = 0
l = [True for i in range(num + m + 1)]
p = 2
while p * p <= num + m:
	if l[p]:
		for i in range(p * p, num + m + 1, p):
			l[i] = False
	p += 1
for p in range(2, num + m + 1):
	if l[p]:
		count += 1
print(count)


(a, b) = map(int, input().split())
n = a + b + 1
isprime = [True] * n
prime = []
SPF = [None] * n

def kk(N):
	isprime[0] = isprime[1] = False
	for i in range(2, N):
		if isprime[i] == True:
			prime.append(i)
			SPF[i] = i
		j = 0
		while j < len(prime) and i * prime[j] < N and (prime[j] <= SPF[i]):
			isprime[i * prime[j]] = False
			SPF[i * prime[j]] = prime[j]
			j += 1
k = 0
kk(n)
i = 0
while i < len(prime) and prime[i] <= n:
	k += 1
	i += 1
print(k)


def sieveOfErathanos(n):
	primes = [1 for i in range(n + 1)]
	primes[0] = primes[1] = 0
	i = 2
	while i * i <= n:
		if primes[i] == 1:
			for j in range(i * i, n + 1, i):
				primes[j] = 0
		i += 1
	return sum(primes)
(n, m) = list(map(int, input().split()))
print(sieveOfErathanos(m + n))


def prime(n):
	if n == 2:
		return 1
	elif n % 2 == 0:
		return int(0)
	else:
		for i in range(3, int(n ** 0.5) + 1, 2):
			if n % i == 0:
				return int(0)
				break
		else:
			return int(1)
(n, m) = map(int, input().split())
t = n + m
a = 0
for j in range(2, t + 1):
	a += int(prime(j))
print(a)


(n1, m) = map(int, input().split())
n = n1 + m
prime = [True for i in range(n + 1)]
p = 2
while p * p <= n:
	if prime[p] == True:
		for i in range(p * p, n + 1, p):
			prime[i] = False
	p += 1
c = 0
for i in range(2, m + n1 + 1):
	if prime[i]:
		c += 1
print(c)


def SieveOfEratosthenes(n, prime):
	p = 2
	while p * p <= n:
		if prime[p] == 1:
			for i in range(p * p, n + 1, p):
				prime[i] = 0
		p += 1
n = 2 * 10 ** 6 + 2
prime = [1 for i in range(n + 1)]
SieveOfEratosthenes(n, prime)
prime[0] = 0
prime[1] = 0
for i in range(1, n + 1):
	prime[i] += prime[i - 1]
(num, m) = map(int, input().split())
print(prime[num + m])


def sieve(n):
	arr = []
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	for p in range(2, n):
		if prime[p]:
			arr.append(p)
	return arr
k = set(sieve(3 * 10 ** 6))
c = 0
(n, m) = [int(x) for x in input().split()]
for i in range(2, n + m + 1):
	if i in k:
		c += 1
print(c)


n = 2000004
prime = [True for i in range(n + 1)]
p = 2
while p * p <= n:
	if prime[p] == True:
		for i in range(p * p, n + 1, p):
			prime[i] = False
	p += 1
a = [0] * 2000005
s = 0
for i in range(2, n + 1):
	if prime[i] == True:
		s += 1
	a[i] = s
(x, y) = map(int, input().split())
print(a[x + y])


(n, m) = map(int, input().split())
n = n + m
prime = [True for _ in range(n + 1)]
p = 2
while p * p <= n:
	if prime[p]:
		for i in range(p * p, n + 1, p):
			try:
				prime[i] = False
			except:
				pass
	p += 1
s = 0
for p in range(2, n + 1):
	if prime[p]:
		s = s + 1
print(s)


def SieveOfEratosthenes(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	total = 0
	for p in range(2, n + 1):
		if prime[p]:
			total = total + 1
	return total
(x, y) = input().split(' ')
x = int(x)
y = int(y)
print(SieveOfEratosthenes(x + y))


from bisect import *
l = []

def SieveOfEratosthenes(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	for i in range(2, n):
		if prime[i]:
			l.append(i)
SieveOfEratosthenes(3 * 10 ** 6 + 123)
(n, m) = map(int, input().split())
ind = bisect_right(l, n + m)
print(ind)


def SieveOfEratosthenes(n):
	c = 0
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	return prime
(n, m) = map(int, input().split())
k = 0
l = list(SieveOfEratosthenes(n + m))
for i in range(2, n + m + 1):
	if l[i] == True:
		k += 1
print(k)


def S(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	g = 0
	for p in range(2, n):
		if prime[p]:
			g = g + 1
	return g
(a, b) = list(map(int, input().split()))
n = a + b
l = S(n + 1)
print(l)


MAX = 2000009
prefix = [0] * (MAX + 1)

def buildPrefix():
	prime = [1] * (MAX + 1)
	p = 2
	while p * p <= MAX:
		if prime[p] == 1:
			i = p * 2
			while i <= MAX:
				prime[i] = 0
				i += p
		p += 1
	for p in range(2, MAX + 1):
		prefix[p] = prefix[p - 1]
		if prime[p] == 1:
			prefix[p] += 1

def query(L, R):
	return prefix[R] - prefix[L - 1]
ll = lambda : list(map(int, input().split()))
[n, m] = ll()
buildPrefix()
print(query(2, n + m))


(n, m) = map(int, input().split())
a = [i for i in range(2, n + m + 1)]
ind = 0
while ind < len(a):
	if a[ind] == 0:
		ind += 1
		continue
	for i in range(ind + a[ind], len(a), a[ind]):
		a[i] = 0
	ind += 1
count = 0
for x in a:
	if x != 0:
		count += 1
print(count)


def sieve(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	primes = 0
	for p in range(2, n + 1):
		if prime[p]:
			primes += 1
	return primes
(n, m) = (int(s) for s in input().split())
primes = sieve(n + m)
print(primes)


def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True

def Prime(n):
	N = 0
	for i in range(2, n + 1):
		N += isPrime(i)
	return N
(n, m) = map(int, input().split())
print(Prime(n + m))


import sys
mod = 1000000007
get_arr = lambda : list(map(int, input().split()))
get_int = lambda : int(input())
get_ints = lambda : map(int, input().split())
get_str = lambda : input()
get_strs = lambda : input().split()
from math import log

def sieve_of_eratosthenes(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p]:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	ans = []
	for i in range(2, n + 1):
		if prime[i]:
			ans.append(i)
	return ans
(n, m) = get_ints()
ans = sieve_of_eratosthenes(n + m)
print(len(ans))