sum-of-primes

Dark  with his love for the prime numbers wanted to do some arithmetic so he decided to do some additions.
He wants to generate all prime numbers between two given numbers and add them up and decide whether that addition of numbers is a prime number or not?

Confused, Simply print "YES"(without quotes) if the sum of prime numbers between two numbers is a prime number and print "NO"(without quotes) if the sum of prime numbers between two numbers is a non-prime number.

Note:

If there are no prime numbers between two given numbers print "NO" (without quotes).

Input:

The first line contains T, the number of test cases.
Followed by T lines each contain two numbers M and N

Output:

For every test case print the YES if sum is a prime number else print NO.

If no prime number between M and N
then print NO.

Constraints

   1 ≤ T ≤ 10000
   1 ≤ M ≤ N ≤ 1000000

Note: 'M' & 'N'  are inclusive.

Author : Darshak Mehta

SAMPLE INPUT
3
1 9
14 37
1 6

SAMPLE OUTPUT
YES
NO
NO

Explanation

Test Case #1:
Prime numbers between 1 to 9 are 2,3,5,7 and their sum is 17 which is a prime number.

Test Case #3:
Prime numbers between 1 to 6 are 2,3,5 and their sum is 10 which is non-prime number

Source: hackerearth | Difficulty: UNKNOWN_DIFFICULTY
Tags: Number theory


Solutions:
import bisect,math

l =[]

def primes_upto(limit):
	is_prime = [False] * 2 + [True] * (limit - 1) 
	for n in range(int(limit**0.5 + 1.5)): # stop at ``sqrt(limit)``
		if is_prime[n]:
			for i in range(n*n, limit+1, n):
				is_prime[i] = False
	return [i for i, prime in enumerate(is_prime) if prime]
	
def iprimes_upto(limit):
	is_prime = [False] * 2 + [True] * (limit - 1)
	for n in range(int(limit**0.5 + 1.5)): # stop at ``sqrt(limit)``
		if is_prime[n]:
			for i in range(n * n, limit + 1, n): # start at ``n`` squared
				is_prime[i] = False
	for i in range(limit + 1):
		if is_prime[i]: yield i
		
		
def iprimes2(limit):
	yield 2
	if limit < 3: return
	lmtbf = (limit - 3) // 2
	buf = [True] * (lmtbf + 1)
	for i in range((int(limit ** 0.5) - 3) // 2 + 1):
		if buf[i]:
			p = i + i + 3
			s = p * (i + 1) + i
			buf[s::p] = [False] * ((lmtbf - s) // p + 1)
	for i in range(lmtbf + 1):
		if buf[i]: yield (i + i + 3)
			
def process():
	global l
#	eratosthenes(1000000,l)
	l = list(iprimes2(1000001))



def is_prime(n):
	if n == 2:
		return "YES"
	if n%2 == 0 or n <= 1:
		return "NO"
	sqr = int(math.sqrt(n)) + 1
	for divisor in range(3, sqr, 2):
		if n%divisor == 0:
			return "NO"
	return "YES"
	
def solve():
	global l
	length = len(l)
	[m,n] = [int(x) for x in input().split()]
	idx = bisect.bisect_left(l,m)
	s = 0
	while idx<length and l[idx]<=n:
		s += l[idx]
		idx += 1
	
	print(is_prime(s))
	
	
def main():
	process()
	for _ in range(int(input())):
		solve()

main()


# Sum of prime number
# import time
import sys
# import os
import math

PRIME_NUMS = [2]

def check_prime(n):
	limit = int(math.sqrt(n))
	idx = 0
	while(PRIME_NUMS[idx] <= limit):
		if n % PRIME_NUMS[idx] == 0:
			return(False)
		idx += 1
	return(True)
	
def main():
	m_list = []
	n_list = []
	no_case = int(sys.stdin.readline())
	for _ in range(no_case):
		m, n = sys.stdin.readline().split()
		m_list.append(int(m) - 1)
		n_list.append(int(n))
	
	maxLimit = max(n_list)
	# maxLimit = 1000000
	prime_sets = set()
	prime_sets.add(2)
	prime_sum = [0, 0, 2]
	flage = [1, 0] * (int(maxLimit / 2) + 1)
	for idx in range(2, maxLimit, 2):
		if flage[idx] == 1:
			PRIME_NUMS.append(idx + 1)
			prime_sets.add(idx + 1)
			prime_sum.append(prime_sum[-1] + idx + 1)
			prime_sum.append(prime_sum[-2] + idx + 1)
			for idx_loop in range(idx, maxLimit, idx+1):
				flage[idx_loop] = 0
		else:
			prime_sum.append(prime_sum[-1])
			prime_sum.append(prime_sum[-1])
	
	result = ""
	for idx in range(no_case):
		current_sum = prime_sum[n_list[idx]] - prime_sum[m_list[idx]]
		if current_sum <= maxLimit:
			if current_sum in prime_sets:
				result += "YES\n"
			else:
				result += "NO\n"
		else:
			if check_prime(current_sum):
				result += "YES\n"
			else:
				result += "NO\n"
			
	sys.stdout.write(result)	

# start_time = time.time()
main()
# print("--- ", time.time() - start_time, " seconds ---")


import bisect,math

l =[]

def primes_upto(limit):
	is_prime = [False] * 2 + [True] * (limit - 1) 
	for n in range(int(limit**0.5 + 1.5)): # stop at ``sqrt(limit)``
		if is_prime[n]:
			for i in range(n*n, limit+1, n):
				is_prime[i] = False
	return [i for i, prime in enumerate(is_prime) if prime]
	
def iprimes_upto(limit):
	is_prime = [False] * 2 + [True] * (limit - 1)
	for n in range(int(limit**0.5 + 1.5)): # stop at ``sqrt(limit)``
		if is_prime[n]:
			for i in range(n * n, limit + 1, n): # start at ``n`` squared
				is_prime[i] = False
	for i in range(limit + 1):
		if is_prime[i]: yield i
		
		
def iprimes2(limit):
	yield 2
	if limit < 3: return
	lmtbf = (limit - 3) // 2
	buf = [True] * (lmtbf + 1)
	for i in range((int(limit ** 0.5) - 3) // 2 + 1):
		if buf[i]:
			p = i + i + 3
			s = p * (i + 1) + i
			buf[s::p] = [False] * ((lmtbf - s) // p + 1)
	for i in range(lmtbf + 1):
		if buf[i]: yield (i + i + 3)
		
		
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] # 2 loops for overflow
	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 # integral number of wheels rounded up
	lmtsqrt = (int(limit ** 0.5) - 7)
	lmtsqrt = lmtsqrt // 30 * 8 + ndxs[lmtsqrt % 30] # round down on the wheel
	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])): # adjust for extras
		if buf[i]: yield (30 * (i >> 3) + modPrms[i & 7])
			
def process():
	global l
#	eratosthenes(1000000,l)
	l = list(primes235(1000001))



def is_prime(n):
	if n == 2:
		return "YES"
	if n%2 == 0 or n <= 1:
		return "NO"
	sqr = int(math.sqrt(n)) + 1
	for divisor in range(3, sqr, 2):
		if n%divisor == 0:
			return "NO"
	return "YES"
	
def solve():
	global l
	length = len(l)
	[m,n] = [int(x) for x in input().split()]
	idx = bisect.bisect_left(l,m)
	s = 0
	while idx<length and l[idx]<=n:
		s += l[idx]
		idx += 1
	
	print(is_prime(s))
	
	
def main():
	process()
	for _ in range(int(input())):
		solve()

main()