Competitive_coding/PRITREE.cpp at master · shashank3395/Competitive_coding · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include<bits/stdc++.h>

using namespace std;

int sieve[40001]={0};

int isprime(int n)
{
    if(sieve[n]==0)
        return 1;
        return 0;
}
int main()
{   sieve[0]=sieve[1]=1;
    for(int i=2;i<40001;i++)
    {
        if(sieve[i]==0)
        {
            for(int j=i;j*i<40001;j++)
                sieve[i*j]++;
        }
    }
    int n;
    cin>>n;
    //n=501;
    int a[n];
    for(int i=0;i<n;i++)
       {
           cin>>a[i];
           //a[i]=i+19;
       }
    int hash1[n]={0};
    int flag=0;
    int counter=0;
    for(int k=1;k<n;k++)
    {
        if(isprime(a[0]+a[k]))
            flag++;
    }
    if(flag==0&&n>1)
    {cout<<1<<" "<<2<<"\n";
      hash1[1]=1;
      //counter++;

    }
    for(int i=0;i<n;i++)
    {
       int parent=0;
        for(int j=i+1;j<n;j++)
        {


            if(isprime(a[i]+a[j])&&hash1[j]!=0&&parent==0&&hash1[i]==0)
                {cout<<j+1<<" "<<i+1<<"\n"; hash1[i]++; parent++; counter++;}
                 if(isprime(a[i]+a[j])&&hash1[j]==0)
                {cout<<i+1<<" "<<j+1<<"\n"; hash1[j]++; counter++;}


        }
         if(hash1[i]==0&&i!=0)
           {
               cout<<1<<" "<<i+1<<"\n";
               hash1[i]++;
               counter++;
           }
    }
    //cout<<"\ncounter is "<<counter;
}