Techgig solution 2021 | Prime Game question solution

Ankur Ranpariya
9 Mar, 2021
12

 

Prime Game 

Rax, a school student, was bored at home in the pandemic. He wanted to play but there was no one to play with. He was doing some mathematics questions including prime numbers and thought of creating a game using the same. After a few days of work, he was ready with his game. He wants to play the game with you.


GAME:

Rax will randomly provide you a range [ L , R ] (both inclusive) and you have to tell him the maximum difference between the prime numbers in the given range. There are three answers possible for the given range.

  1. There are two distinct prime numbers in the given range so the maximum difference can be found.

  2. There is only one distinct prime number in the given range. The maximum difference in this case would be 0.

  3. There are no prime numbers in the given range. The output for this case would be -1.


To win the game, the participant should answer the prime difference correctly for the given range.


Example:

Range: [ 1, 10 ]

The maximum difference between the prime numbers in the given range is 5.

Difference = 7 - 2 = 5


Range: [ 5, 5 ]

There is only one distinct prime number so the maximum difference would be 0.


Range: [ 8 , 10 ]

There is no prime number in the given range so the output for the given range would be -1.


Can you win the game?



Input Format

The first line of input consists of the number of test cases, T

Next T lines each consists of two space-separated integers, L and R



Constraints

1<= T <=10

2<= L<= R<=10^6



Output Format

For each test case, print the maximum difference in the given range in a separate line.

Sample TestCase 1
Input
5
5 5
2 7
8 10
10 20
4 5
Output
0
5
-1
8
0













Explanation

Test Case 1: [ 5 - 2 ] = 3

Test Case 2: [ 7 - 2 ] = 5

Test Case 3: No prime number in the given range. Output = -1

Test Case 4: [ 19 - 11 ] = 8

Test Case 5: The difference would be 0 since there is only one prime number in the given range.

Now code is improved it run all the test cases



Solution in python3

def main():

    testCase = int(input())
    def isprime(n):
        if n<=1:
            return False
        for i in range(2,n):
            if n%i ==0:
                return False
        return True
    
    while testCase >0:
        LR = list(map(int,input().strip().split()))
        first = LR[0]
        last = LR[1]
        f = 0
        l = 0
        for i in range(first,last+1):
            if f ==0:
                if isprime(i):
                    f=i
                else:
                    i = i+1
            if l==0:
                if isprime(last):
                    l=last
                else:
                    last -=1
            if f!=0 and l!=0:
                break
            
        if f!=0 and l!=0:
            print(l-f)
        else:
            print(-1)
        
        testCase -=1

main()










How to optimize this code and a full explanation of this code

If you have a better solution than me then please comment on it.


Next Post Previous Post
12 Comments
  • Utsab
    Utsab March 29, 2021 at 8:10 PM

    Answer is not correct

    Reply
  • General Techdost
    General Techdost April 2, 2021 at 2:26 PM

    just only pass in test case

    Reply
  • lappy
    lappy April 5, 2021 at 1:59 PM

    TLE in all cases except sample case

    Reply
  • NOOBprogrammer
    NOOBprogrammer April 6, 2021 at 12:10 AM

    Test case failures

    Reply
  • Unknown
    Unknown April 10, 2021 at 1:15 PM

    It is getting error in all test case {Time Limit exceeded}

    Reply
  • Anonymous
    Anonymous April 11, 2021 at 1:00 PM

    def main():
    testCase = int(input())

    while testCase>0:
    LR = list(map(int,input().strip().split()))
    L = LR[0]
    R = LR[1]
    lst=[]
    flag=1
    for i in range(L,R+1):
    isPrime = True
    for num in range(2, int(i ** 0.5) + 1):
    if i % num == 0:
    isPrime = False
    flag = -1
    break
    if isPrime:
    lst.append(i)

    n=len(lst)
    if n>1:
    print(max(lst)-min(lst))
    elif n==1:
    print(0)
    elif flag==-1:
    print(-1)

    testCase -=1
    main()

    Reply
  • Unknown
    Unknown April 11, 2021 at 10:20 PM

    time exceeded error

    Reply
  • Ankur Ranpariya
    Ankur Ranpariya April 12, 2021 at 10:32 AM

    Now code is improve, see the solution.

    Reply
  • Unknown
    Unknown April 18, 2021 at 4:26 PM

    This comment has been removed by a blog administrator.

    Reply
  • Unknown
    Unknown April 21, 2021 at 9:38 PM

    This comment has been removed by a blog administrator.

    Reply
  • nmd stark
    nmd stark May 7, 2021 at 1:44 PM

    Working Successfully... :)

    Reply
  • nmd stark
    nmd stark May 7, 2021 at 1:46 PM

    working successfully.. :)

    Reply
Add Comment
comment url