L’idea credo sia giusta, ma il programma sbaglia degli output, totalizzando solamente 40/100.
Ecco il codice:
#include <bits/stdc++.h>
using namespace std;
int a, b;
bool primo[38600];
vector <int> v;
void crivello()
{
for(int i=2; i< 35001; i++)
primo[i] = true;
for(int i=2; i<=sqrt(35001); i++)
{
if(primo[i])
{
for(int j= i+i; j < 35001; j+=i)
{
primo[j]=false;
}
}
}
return;
}
int minimoComuneDivisore(int uno, int due)
{
unordered_set <int> divisori_uno;
int copia = uno, indice = 0;
while(copia > 1) // scomposizione in fattori primi (poi inseriti nell' unordered_set)
{
while(copia%v[indice] == 0)
{
copia/=v[indice];
divisori_uno.insert(v[indice]);
}
indice++;
}
copia = due, indice = 0;
while(copia > 1)
{
while(copia%v[indice] == 0)
{
copia/=v[indice];
if(divisori_uno.find(v[indice]) != divisori_uno.end())
return v[indice];
}
indice++;
}
return 1;
}
int primo_con_a() // trova il primo numero i tale che (a, i) siano primi tra loro (ovvero non hanno divisori comuni)
{
for(int i=20; i<35000; i++)
if(minimoComuneDivisore(a, i) == 1)
return i;
}
int main(){
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
cin >> a >> b;
crivello();
for(int i=0; i< 35001; i++)
if(primo[i])
v.push_back(i); // vector con tutti i numeri primi minori di 35 000
cout << a/minimoComuneDivisore(a, b) << " " << primo_con_a();
return 0;
}
grazie in anticipo!
