/* 
 * File:   main.cpp
 * Author: Micren
 *
 * Created on 16 Январь 2011 г., 16:49
 */

#include <iostream>
#include <iomanip>
#include <locale>
#include <limits>

using namespace std;

typedef unsigned int uint;

// Используется для ввода данных

template<class T>
T input(const char* const msg)
{
    T res = 0;
    while (true)
    {
        cout << msg;
        cin >> res;
        if (cin.fail())
        {
            cin.clear();
            cin.ignore(numeric_limits<streamsize>::max(), '\n');
            cout << "Ошибка ввода." << endl;
        }
        else
        {
            return res;
        }
    }
}

// Наибольший общий делитель

uint nod(uint a, uint b)
{
    while (a && b)
    {
        if (a > b)
        {
            a %= b;
        }
        else
        {
            b %= a;
        }
    }
    return a | b;
}

/*
 *
 */
int main()
{
    locale::global(locale(""));

    uint p = input<uint > ("Введите p:"), q = input<uint > ("Введите q:");

    cout << "Делители " << q << " взаимно простые с " << p << ":" << endl;

    size_t count = 0;

    for (uint i = 0; i++ < q;)
    {
        if (q % i == 0 && nod(i, p) == 1)
        {
            ++count;
            cout << i << ",";
        }
    }

    if (count)
    {
        cout << "\b " << endl;
    }
    else
    {
        cout << "Нет таких" << endl;
    }

    system("pause");
    
    return 0;
}

Введите p:15
Введите q:25
Делители 25 взаимно простые с 15:
1

Введите p:125
Введите q:1023
Делители 1023 взаимно простые с 125:
1,3,11,31,33,93,341,1023 

#include <iostream>

// Вычисление НОД с помощью алгоритма Евклида
unsigned nod(unsigned a, unsigned b)
{
  unsigned n = (a > b) ? a : b;
  unsigned m = (a > b) ? b : a;
  while (m != 0)
  {
    unsigned r = n % m;
    n = m;
    m = r;
  }
  return n;
}

int main()
{
  unsigned q, p;
  std::cout << "Введите p, q: ";
  std::cin >> p >> q;

  std::cout << "Делители: { ";
  for (unsigned d = 1; d <= q; ++d)
  {
    if ((q % d) == 0 && nod(d, p) == 1)
      std::cout << d << ' ';
  }
  std::cout << "}\n";

  system("pause");
  return 0;
}