# Aiuto problema giostre

**URL:** <https://forum.olinfo.it/t/aiuto-problema-giostre/4760>\
**Category:** Aiuto\
**Created:** [10 Agosto 2017, 2:55pm UTC](https://forum.olinfo.it/t/aiuto-problema-giostre/4760 "2017-08-10T14:55:18Z")\
**Posts on this page:** 4\
**Page:** 1

<div class="post-metadata">

**Author:** ![Spippolino01](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/s/a88e4f/32.png) [@Spippolino01](https://forum.olinfo.it/u/Spippolino01)\
**Post date:** [10 Agosto 2017, 2:55pm UTC](https://forum.olinfo.it/t/aiuto-problema-giostre/4760/1 "2017-08-10T14:55:18Z")

</div>

L’idea credo sia giusta, ma il programma sbaglia degli output, totalizzando solamente 40/100.  
Ecco il codice:

```auto
#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!

---

<div class="post-metadata">

**Author:** ![dp\_1](https://forum.olinfo.it/user_avatar/forum.olinfo.it/dp_1/32/2635_2.png) [@dp\_1](https://forum.olinfo.it/u/dp_1)\
**Post date:** [10 Agosto 2017, 3:01pm UTC](https://forum.olinfo.it/t/aiuto-problema-giostre/4760/2 "2017-08-10T15:01:27Z")

</div>

Che algoritmo usi per l’MCD? L’algoritmo di Euclide è molto più semplice in teoria e da implementare.

---

<div class="post-metadata">

**Author:** ![Spippolino01](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/s/a88e4f/32.png) [@Spippolino01](https://forum.olinfo.it/u/Spippolino01)\
**Post date:** [10 Agosto 2017, 3:05pm UTC](https://forum.olinfo.it/t/aiuto-problema-giostre/4760/3 "2017-08-10T15:05:23Z")

</div>

in realtà non cerca l’MCD, bensì il minimo comune divisore (se hanno altri divisori comuni oltre ad 1, ne restituisce il minimo escludendo 1)

EDIT: ho risolto: l’ errore stava nella formula del primo intero da stampare…è meglio fare la simulazione!

---

<div class="post-metadata">

**Author:** ![dp\_1](https://forum.olinfo.it/user_avatar/forum.olinfo.it/dp_1/32/2635_2.png) [@dp\_1](https://forum.olinfo.it/u/dp_1)\
**Post date:** [10 Agosto 2017, 6:46pm UTC](https://forum.olinfo.it/t/aiuto-problema-giostre/4760/4 "2017-08-10T18:46:00Z")

</div>

Scusami allora, ho letto rapidamente la domanda 😅