3
\$\begingroup\$

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;
}
\$\endgroup\$
0

5 Answers 5

5
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ Original sultion might be a bit better because it takes into account the fact that we need to find set of co-primes rather than check one particular pair. \$\endgroup\$
    – ony
    Jan 13, 2014 at 9:19
0
\$\begingroup\$

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++;
}
\$\endgroup\$
1
  • \$\begingroup\$ Didn't you've lost populating num vector? \$\endgroup\$
    – ony
    Jan 13, 2014 at 8:15
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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));
}
\$\endgroup\$
2
  • \$\begingroup\$ Euler's totient function \$\endgroup\$
    – Gs_
    Jun 7, 2017 at 13:16
  • 2
    \$\begingroup\$ This is basically a code dump answer (even after moving the explanatory text to the top). Every answer must make at least one insightful observation about the code in the question and not just offer an alternative implementation without at least explaining what it does better or how. See the help-center for more information. \$\endgroup\$
    – Graipher
    Jun 7, 2017 at 13:36
0
\$\begingroup\$

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;
\$\endgroup\$
2
  • \$\begingroup\$ What's wheel? \$\endgroup\$ Jan 13, 2014 at 12:07
  • \$\begingroup\$ @200_success That was in ony's code. I forgot to delete it. It's removed now. Thanks. \$\endgroup\$ Jan 13, 2014 at 12:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.