roy-and-rangoli-1

Its Diwali time and little Roy thought of an interesting design for Rangoli.
He created an N x N grid. Roy fills some of the cells of grid with red color.

Cell located at ith row and jth column is colored if i+j is prime. Consider Zero-based numbering of grid. (See Sample Test Case Explanation for clarification)

Roy wants to know how many cells he will have to color given the size of grid N.

Input:

One integer indicating size of grid N

Output:

Print a single integer, number of cells Roy will have to color. Since answer can be very large output it modulo 1000000007

Constraints:

1 ≤ N ≤1000000

Sample Test Case Explanation:SAMPLE INPUT
3

SAMPLE OUTPUT
5

Explanation

As shown in the image above, five cells (0,2), (1,1), (1,2), (2,0), (2,1) are colored red because for (i,j) i+j for these cells results into a prime number.

Source: hackerearth | Difficulty: MEDIUM
Tags: Implementation

Mathematics


Solutions:
def sieve(n):
	is_prime = [True] * (n+1)
	is_prime[0] = is_prime[1] = False
	for i in range(2, n+1):
		if is_prime[i]:
			for j in range(i+i, n+1, i):
				is_prime[j] = False
	return is_prime

n = int(input())
is_prime = sieve(n+n)
total = 0
for i in range(n):
	if is_prime[i]:
		total += i+1
nn1 = n+n-1
for i in range(n, nn1):
	if is_prime[i]:
		total += nn1 - i

print(total % 1000000007)



'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
def isPrime(n):
	for i in range(2,int(n**0.5)+1):
		if n%i==0:
			return False

	return True
def sieve1(limit):
	limitn = limit+1
	primes = dict()
	for i in range(2, limitn): primes[i] = True

	for i in primes:
		factors = list(range(i,limitn, i))
		for f in factors[1:]:
			primes[f] = False
	return [i for i in primes if primes[i]==True]
a=eval(input())
c=0
d=0
b=sieve1(2*(a-1))
for j in range(0,len(b)):
	if((a-1)>=b[j]):
		c+=b[j]+1
	elif(a==b[j]):
		c+=b[j]-1
	else:
		d+=(a-1)-(b[j]-(a-1))+1
print(((c+d)%1000000007))


import math

'''
n = 9
8
i-(n-1)
max = 16
16-8 = 8
16 = 8+8 -> 1
15 = 7+8 = 8+7 2
14 3 6
13 4 5
8 5, 7 6, 6 7, 5 8

15 -> 16-15+1



'''

primes = {2: True, 3: True}
primesArray = [2,3]
largest = {"prm": 3}
n = int(input())
size =  (n-1) * 2
m = 1000000007


def isPrime(n):
	if n%2 == 0:
		return False

	sqrt = int(math.sqrt(n))
	for i in primesArray:
		if i > sqrt: break
		if i == n : return True
		if n % i == 0: return False

	for i in range(largest["prm"], sqrt+1, 2):
		if n % i == 0: return False

	primes[n] = True
	primesArray.append(n)
	largest["prm"] = max(largest["prm"], n)
	return True

for i in range(3,size+1):
	isPrime(i)

count = 0
for i in range(2,size+1):
	if i in primes:
		if i <= n-1:
			count = (count + i + 1) % m
		if i > n-1:
			count = (count + size - i + 1) % m

print(count)


__author__ = 'Admin'

limit = int(input())
if limit == 1:
	print(0)
else:
	limit = limit - 1
	list_of_primes = []
	for i in range(0 , limit * 2 + 1):
		list_of_primes.append(0)
	list_of_primes[0] = 1
	list_of_primes[1] = 1
	i=2
	while(i * i <= limit*2):
		if list_of_primes[i] == 0:
			k = 2
			j = i * k
			while(j <= limit*2):
				list_of_primes[j] = 1
				k = k + 1
				j = i * k
		i = i + 1

	# print list_of_primes
	cnt = 0
	for i in range(0 , limit+1):
		if list_of_primes[i] == 0:
			cnt = cnt + (i+1)
			cnt = cnt % 1000000007
	j = limit
	i = limit+1
	while(i < limit*2 + 1):
		if list_of_primes[i] == 0:
			cnt = cnt + (j)
			cnt = cnt % 1000000007
		j = j - 1
		i = i + 1

	print(cnt)



MOD = 1000000007
N = 2000001
prime = [0]*N
prime[0] = 1
prime[1] = 1
def sieve():
	i = 2
	while i*i <= N:
		j = 2*i
		if prime[i] != 1: 
			while j < N:
				prime[j] = 1
				j += i
		i += 1
def roy_and_rangoli():
	G = eval(input())
	sieve()
	res = 0
	for i in range(G):
		if prime[i] == 0:
			res = res + i + 1
			res %= MOD
	#print res
	for i in range(G,2*G-1):
		if prime[i] == 0:
			t = (i+1) - 2*(i-(G-1))
			#t %= MOD
			res += t
			res %= MOD
	print(res)
roy_and_rangoli()


def isPrime(n):
	for i in range(2,int(n**0.5)+1):
		if n%i==0:
			return False

	return True
def primes_sieve1(limit):
	limitn = limit+1
	primes = dict()
	for i in range(2, limitn): primes[i] = True

	for i in primes:
		factors = list(range(i,limitn, i))
		for f in factors[1:]:
			primes[f] = False
	return [i for i in primes if primes[i]==True]
a=eval(input())
c=0
d=0
b=primes_sieve1(2*(a-1))
for j in range(0,len(b)):
	if((a-1)>=b[j]):
		c+=b[j]+1
	elif(a==b[j]):
		c+=b[j]-1
	else:
		d+=(a-1)-(b[j]-(a-1))+1
print(((c+d)%1000000007))