Geeksforgeeks,practice,return two prime numbers,solution

Hi guys, In this post we would solve a problem of "geeksforgeeks"; "return two prime numbers".
those who are not gone through the problem here it is.

QUESTION:

Return two prime numbers

Submissions: 6675   Accuracy: 

61.46%

   Difficulty: Hard   Marks: 8

Associated Course(s):   Sudo Placement [IITs]

    

    

Given an even number ( greater than 2 ), return two prime numbers whose sum will be equal to given number. There are several combinations possible. Print only first such pair. 

NOTE: A solution will always exist, read Goldbach’s conjecture.

Also, solve the problem in linear time complexity, i.e., O(n).

Input:

The first line contains T, the number of test cases. The following T lines consist of a number each, for which we'll find two prime numbers.

Note: The number would always be an even number.

 
Output:

For every test case print two prime numbers space separated, such that the smaller number appears first. Answer for each test case must be in a new line.

Constraints:

1 ≤ T ≤ 70
1 ≤ N ≤ 10000

Example:

Input:

5
74
1024
66 
8
9990

Output:

3 71
3 1021
5 61
3 5
17 9973

Visit this link for more details about question.

https://practice.geeksforgeeks.org/problems/return-two-prime-numbers/0

THE CODE :
int checkprime(int);
void main()
{
    int t;
    scanf("%d\n",&t);
    for(int i=0;i<t;i++)
    {
        int n;
        scanf("%d",&n);
        int flag=0,j=n;
        while(flag!=1)
        {
            if(checkprime(j)==1)
            {
                int pole=0,k=3;
                while(pole!=1)
                {
                    if(checkprime(k)==1)
                    {
                       if((k+j)==n)
                       {
                           pole=1;
                           flag=1;
                           printf("%d ",k);
                           printf("%d",j);
                       }
                    }
                    if(k>=j)
                    {
                        pole=1;
                    }
                    k+=1;
                }
            }
            j=(j-1);
        }
        printf("\n");
    }
}
int checkprime(int p)
{
   int r;
   for(int q=2;q<p;q++)
   {
       r=p%q;
       if(r==0)
       {
           return 0;
       }
   }
   return 1;
}
EXPLANATION :
first we would take input 't' as no of test cases required.
'for'  loop following it will run the program  no of test cases (t) times.
now comming to function checkprime() whose work is to take a integer from main() function as 'p' and check  'p' for prime and return 1 if it is a prime no else return 0.  for this to work we have used r=p%q (where q is a variable which vary from 2 to (p-1) ) .
if r%p=0,we have got a facter of 'p' in between 1 and p, and function checkprime() returns 0;if not after checking q for all values from 2 to (p-1) if it cannot find a factor then as soon as for loop ends it will return 1.
now comming to the main() function;
what we are going to do is choosing a no 'j' equal to (n-1),check it for prime,if it is not prime ,we would assign j=(n-2);but if it is prime we would choose a no k=3,we are assigning initial of k as 3 because 1 is not a prime and  sum of 2 with a prime cannot be an even no(n),after checking k for prime ,if it turns true i .e k is prime we will check k+j=n, if true print j and k ,and flag and pole  make sure that as soon as  values for j and k are printed  controls come out of both loops and next test case is ready to begin,if  false  increase k by 1, and do the same process ; after checking to all values of k  i.e if k>=j we assign pole=1 since we cannot find a k where k<=n ,for this particular j=(n-1) ,such that k+j=n,so we now reduce j by 1 by moving controls to j-=1 and will check again for all prime k<=j such that k+j=n;if values of j and  k are found print them and flag and pole move the control out of both loops for a fresh test case otherwise ,reduce j by 1 and repeat the process until we get values for j and k because they exists for every prime number.
Hope you liked it don't forget to give precious comments . What do u like to read here and how can
we explain better ;
See u in next post cheers.