Gfrktyl

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;

}

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.

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++;

}

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.

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));

}

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;