TNQT Digital 2 Coding Question

general
,
1

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
2

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
3
2 Likes
4

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

1 Like
5

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

3 Likes
6

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
7

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

1 Like
8

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
9

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
10

Yes, I did the same.

11

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))

12

how you come up with this pattern @roha2

13

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

14

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.

15

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

16

how? can u do better than sieve?

17

where u gave manually input , there is no option

18

how can u do that…??

19

@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.

20

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