TNQT Digital 2 Coding Question

This question was asked today in TNQT Digital 2 Exam
Find how many Sexy Prime Numbers in a given range n and m.
Constraint: 2 <= n < m <= 1000,000,000.

Sample Input:
4 40
Output:
7

Explanation:
[5,11]
[7,13]
[11,17]
[13,19]
[17,23]
[23,29]
[31,37]

How to solve this for given constraint?

1 Like

I think it’s a pattern question.If u see,each pair can be represented as (6n+1,6(n+1)+1) or (6n-1,6(n+1)-1).But I failed to notice this during test&tried Sieve which obviously gave TLE.

1 Like
1 Like

Please don’t flag this XD
This is the real name i swear!!

1 Like

I also solved using Sieve and able to passed 6/7 test cases. I used sieve only for 10^6.

2 Likes

I failed to even get them too.Did you use boolean array of 10^6& then sieve?I got TLE for this solution also.

1 Like

okk… now u see the pattern tell us how to do that better than sieve???

1 Like

used vector of bool of size n+1
found all primes <= n (n given in input) using seive O(n*log(log(n)))
incremented answer for all numbers in range m to n-6 such that both m and m+6 are prime.
This passed all 7 Test cases but when I manually gave m=2, n=10^9 it timed out.

2 Likes

I tried using sqrt method but it said “Process killed after 2.0000 seconds.”
If C and C++ has 2 sec time limit, shouldn’t python have 10 sec?
If they’d have mentioned it, I’d have started with C++. Didn’t have enough time to do it over in C++.

2 Likes

Yes, I did the same.

test=input()

start,end=test.split(" ")

prime=[]

output=[]

#print(start)

start=int(start)

end=int(end)

for i in range(start,end+1):

count=0

for j in range(2,i):
    
    if(i%j==0):
        
        count=count+1

if count==0:
    prime.append(i)

prime.sort()

for k in range(len(prime)):

for l in  range(len(prime)):
    
    if (prime[k]-prime[l]==6):
        
        output.append(prime[k])
        
        break

print(output)

print(len(output))

how you come up with this pattern @roha2

Sieve didn’t gave me TLE, passed all 7 test cases

Actually it is already widely known that except 2 and 3, all prime numbers are either (6N-1) or (6N+1). I never came across this so could not solve it under given time constraint.

i guess test cases were weak, normal sieve wont work also we would require linear sieve or normal sieve with some modification.
blog:

how? can u do better than sieve?

where u gave manually input , there is no option

how can u do that…??

@tarang4 I didn’t know this so I couldn’t do it on the test. I just found out when @roha2 mentioned this in the second post on this thread.

n was not more than 10^7 in any test case as some of my friends passed all 7 test cases by creating sieve up to just 10^7