Relative prime numbers

Question

Two integers a and b are relatively prime if and only if there are no integers:

x > 1, y > 0, z > 0 such that a = xy and b = xz.

I wrote a program that determines how many positive integers less than n are relatively prime to n. But my program works too slowly because the number is sometimes too big.

My program should work for n <= 1000000000.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    long long int n;
    int cntr = 0, cntr2 = 0;
    cin >> n;
    if (!n) return 0;
    vector <int> num;
    for (int i = 2; i < n; i++)
    {
        if (n % i != 0)
        {
            if (num.size()>0)
            {
                for (int j = 0; j < num.size(); j++)
                {
                    if (i % num[j] != 0)
                        cntr2++;
                }
                if (cntr2 == num.size())
                    cntr++;
                cntr2 = 0;
            }
            else
                cntr++;
        }
        else
            num.push_back(i);
    }
    cout << cntr + 1 << endl;
}

Answer 1

In order to determine whether two numbers are co-prime (relatively prime), you can check whether their gcd (greatest common divisor) is greater than 1. The gcd can be calculated by Euclid's algorithm:

unsigned int gcd (unsigned int a, unsigned int b)
    {
      unsigned int x;
      while (b)
        {
          x = a % b;
          a = b;
          b = x;
        }
      return a;
    }

if gcd(x,y) > 1: the numbers are not co-prime.

If the code is supposed to run on a platform with slow integer division, you can use the so called binary gcd instead.

Answer 2

Your code can be simplified by eliminating a special case. This…

if (n % i != 0)
{
    if (num.size()>0)
    {
        for (int j = 0; j < num.size(); j++)
        {
                if (i % num[j] != 0)
                cntr2++;
        }
        if (cntr2 == num.size())
            cntr++;
        cntr2 = 0;
    }
    else
        cntr++;
}

… can be written as:

if (n % i != 0)
{
    int cntr2 = 0;
    for (int j = 0; j < num.size(); j++)
    {
        if (i % num[j] != 0)
            cntr2++;
    }
    if (cntr2 == num.size())
        cntr++;
}

Furthermore, you could eliminate cntr2. Breaking from the loop earlier saves work and should improve performance.

if (n % i != 0)
{
    for (int j = 0; j < num.size(); j++)
    {
        if (i % num[j] == 0)
        {
            cntr--;
            break;
        }
    }
    cntr++;
}

Answer 3

Suggestions from @200_success will bring you speedup like from ~28.1s to ~11.8s (gcc 4.8.2 with -O3). Replacing all with gcd as suggested @EOF will give you ~11.4s and will save some memory.

Overall idea is somewhat correct. You collect factors of n and check that there is no factors within other numbers (that are not already factors of n).

But I guess you can improve solution by factoring with primes and avoid populating num with numbers like 4, 6, 8, 9 etc. That brings time to ~1.3s.

for (int i = 2; i < n; i++)
{
    if (n % i == 0)
    {
        bool foundFactor = false;
        for (int j = 0; j < num.size(); ++j)
        {
            if (i % num[j] == 0)
            {
                foundFactor = true;
                break;
            }
        }
        if (!foundFactor) num.push_back(i);
        continue;
    }
    bool foundFactor = false;
    for (int j = 0; j < num.size(); ++j)
    {
        if (i % num[j] == 0)
        {
            foundFactor = true;
            break;
        }
    }
    if (!foundFactor)
        cntr++;
}

For your n = 1000000000 I've got ~13.6s

Note that there is a linear relation beetween numbers of co-primes in 1000000000 and 1000. That's because the only difference between them is (2*5)**k. That leads us to another optimization based on the wheel factorization:

long long wheel = 1;

// factorization of n
for (long long i = 2, m = n; i <= m; i++)
{
    if (m % i == 0)
    {
        num.push_back(i);
        wheel *= i; // re-size wheel
        // remove powers of i from m
        do { m /= i; } while (m % i == 0);
    }
}

for (int i = 2; i < wheel; i++)
{
    if (n % i == 0)
    {
        continue;
    }
    bool foundFactor = false;
    for (int j = 0; j < num.size() && num[j] < i; ++j)
    {
        if (i % num[j] == 0)
        {
            foundFactor = true;
            break;
        }
    }
    if (!foundFactor)
        cntr++;
}
cout << cntr+1 << endl;
cout << (cntr+1)*n/wheel << endl;

That gives ~0s for almost any 10**k

P.S. It sound pretty much as Project Euler problem I've met once. I used a bit different approach. I already had a pretty good framework for working with primes and I just simply generated all numbers out of primes that have no factors of n initially. I.e. built up sequence of combinations 3**k * 7**k ... until they've reached n.

Answer 4

I don't know if you still need this, since it is a very old question. I wrote it for anybody else who might be looking for the answer.

This counts every N's "relatively prime number" (less then N). It is called Eulers' totient function.

#include <cstdio>
typedef long long lld;

lld f(lld num)
{
    lld ans = num;
    for (lld i = 2; i*i <= num; i++)
    {
        if (num%i==0)
        {
            while (num%i==0) num /= i;
            ans -= ans / i;
        }
    }
    if (num > 1)
        ans -= ans / num;
    return ans;
}

int main()
{
    lld N;
    scanf("%lld", &N);
    printf("%lld", f(N));
}

Answer 5

Gs_'s answer starts off by essentially finding all the prime factors of n. If you're going to do that, then you might as well use the following well-known formula that calculates the Euler function from the prime factorisation:

phi(p1 ^ a1 * ... * pk ^ ak) =
      (p1 ^ a1 - p1 ^ (a1 - 1))
    * ...
    * (pk ^ ak - pk ^ (ak - 1))

The code would look something like this:

long long phi = 1;

// factorization of n
for (long long i = 2, m = n; m > 1; i++)
{
    // Now phi(n/m) == phi
    if (m % i == 0)
    {
        // i is the smallest prime factor of m, and is not a factor of n/m
        m /= i;
        phi *= (i - 1);
        while (m % i == 0) {
            m /= i;
            phi *= i;
        }
    }
}

return phi;