Дано натуральное число k. Получите все натуральные числа, меньшие k и взаимно простые с ним

#include <iostream>
#include <conio.h>
using namespace std;
bool Simple (int &N)// ф-ия проверяет является ли число простым, нсли да то возвращает true
{
    bool rez=true;
    for(int k=2;k<=N/2;k++)
    if (N%k==0) rez=false;
    return rez;
}
int main()
{
    setlocale(0,"Rus");// для вывода русских букв на экран
    int k;// здесб будет хранится вводимое число
    cout<<"Введите число: ";cin>>k;
    cout<<"Все простые и натуральные числа меньше "<<k<<endl;
    for(int i=1;i<k;i++)// в этом цикле проверяем все числа до k , простые они или нет
    {
        if(Simple(i)) cout<<i<<" ";// если простое то выводим его на консоль
    }
    getch();
    return 0;
}

#include <iostream>
 
int NOD(int a,int b)
 {
    while(a!=0 && b!=0)
    {
       if(a>=b) a=a%b;
           else b=b%a;
    }
 return a+b;
 }
 
int main()
{
    int n;
    std::cout<<"Input k->";
    std::cin>>n;
    for(int i=1;i<n;i++)
        if(NOD(i, n)) std::cout << i<< " ";
//system("Pause"); may needed in #include <cstdlib> [C++] or <stdlib.h> [C]
    return 0;
}