Prime visits pls explain the question

#1

PMO gives two random numbers a & b to the Prime Minister. PM Modi wants to visit all countries between a and b (inclusive) , However due to shortage of time he can’t visit each and every country , So PM Modi decides to visit only those countries,for which country number has two divisors. So your task is to find number of countries Mr. Modi will visit.

1 Like
#2

Hey Ankush, the problem is pretty simple as
a number has two divisors means the number should be prime as first divisor is 1 and second is the number itself.
So, you are supposed to find the count of prime numbers between two given prime numbers a and b.

#3

test case #3 says time limit pls tell what does it mean how can we come over this

#4

here is my code https://ide.codingblocks.com/s/53186

#5

your normal approach to find a number is prime or not will give TLE, as Time complexity will become O(n*n).

Hint : you have to use sieve of eratosthene and Segmented sieve Study these topics and apply the concept.

Hit like if you get it!
Cheers!

#6

again show run time error in #3 test case https://ide.codingblocks.com/s/53852

#8

Hi Ankush, you don’t need to generate the sieve again and again for every testcase. Just generate it once, and use it for every testcase.

#9

still run-error ehhhhhhhh this problem sucks man; pks check out my code : https://ide.codingblocks.com/s/54070

#10

Hi Ankush, because you’re still making the sieve again and again. Everytime you’ll call the sieve function, a new sieve will be constructed.

1 Like
#11

upto which no should i genrete the sieve

#12

https://ide.codingblocks.com/s/54230 still run time error

#13

The stack memory allotted in main function is less, so instead of creating the array inside main, we will keep it global. Also, since integer takes more bytes than boolean variables, we will create the array of boolean instead of int. These changes will help in reducing the space complexity.
I’ve made these changes to your code and it’s working now. You can refer to it here.
https://ide.codingblocks.com/s/54270
In case of further doubts, you can reply to this thread.

1 Like
#14

Not Able to understand what’s the problem in my code everything is correct but test case 2 and 3 are failing please help.

a=[]
for i in range(1000001 ):
	a.append(0)
for i in range(3,1000001 ,2):
	a[i]=1
for i in range(3,1000001 ,2):
	if(a[i]==1):
		for j in range(i*i,1000001 ,i):
			a[j]=0
a[2]=1

a1=a
for i in range(1,len(a1)):
    a1[i]+=a1[i-1]

for _ in range(int(input())):
	x,y=map(int,input().split())
	print(a1[y]-a1[x-1])