# ProblematicPublicKeys

On February 15, 2012, the New York Times reported a flaw in the method of generating keys for a public-key encryption system (“Researchers Find a Flaw in a Widely Used Online Encryption Method" by John Markoff). This flaw enables an attacker to determine private keys given a set of flawed public keys.
Your job is to write a program that takes flawed public keys and determines the corresponding private keys. For the purposes of this problem, a private key consists of a pair of prime numbers,

2 < K1,K2 < 2^31

and the corresponding public key consists of the product K1 * K2.

Input
The first line of the input contains an integer value, M (2 <= M <= 100). M is the number of input lines that follow. Each of the M lines contains a single “public key." Each public key is the product of exactly two prime numbers and will fit in a 32-bit unsigned integer.

Output
The output lines produced by your program should contain the unique prime factors of the input data values in ascending numeric order, five per line, except for the last line. Output values on the same line are separated by a single space.

Sample Input
6
221
391
713
1457
901
299

Sample Output
13 17 23 31 47
53

Sample Input 2
2
2143650557
2140117121

Sample Output 2
32717 65413 65521

``````#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll prime;
bool check;
set<ll> st;
void f()
{
memset(check,true,sizeof(check));
check=false;
ll n,count;
n=100000;
count = 0;
for (int i = 2; i <n; i++)
{
if (check[i])
prime[count++] = i;
for (int j = 0; j < count&&i*prime[j]<100000; j++)
{
check[i*prime[j]] = false;
if ( (i%prime[j]) == 0 )
break;
}
}//cout<< prime <<endl;
}
int main()
{
f();
//	cout<< prime <<endl;
ll n;
cin>>n;
for(ll i=0;i<n;i++)
{
ll a;
cin>>a;
ll j=0;
while(1)
{
if(a%prime[j]==0)
{
st.insert(prime[j]);
st.insert(a/prime[j]);
break;
}
j++;
}
}
ll i=0;
set<ll>::iterator it;
for(it=st.begin();it !=st.end();++it)
{
it++;
if(it==st.end())
break;
it--;
i++;
if(i%5==0)
cout<<*it<<'n';
else
{
cout<<*it<<" ";
}
}

it--;
cout<<*it<<endl;

return 0;
}
``````

• • 