Relative prime numbers [closed]

Question

Closed. This question needs details or clarity. It is not currently accepting answers.

---

Want to improve this question? Add details and clarify the problem by editing this post.

Closed 8 years ago.

Improve this 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 program that determine how many positive integers less than n are relatively prime to n, but my program work too slow because sometimes number is too big. Can you fix my program.
My program should work for n<=1000000000
Here is my code:

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

int main()
{
    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

You need to do two things:

1. test fewer numbers
2. test them faster

Regarding point 1 - there are a number of things you can do. First - if n is even, there is no point in checking even numbers - so you can increment the "number to test" by 2. If n is divisible by 3, you can skip every third number. This is fairly easy to implement and will speed your code up for some numbers. The methos that Richard Plunkett outlined will help somewhat with point 2. I think there are much faster algorithms; I'll give it some thought.

Answer 2

There are many things you can do to make this task go faster. Your approach is O(N^2), which strikes me as very poor.

A first pass at a simple faster version, would be to change your rel-prime test to using GCD.

for (int i = 2; i < n; i++)
{
   if (GCD(i,n)==1) cntr++
}
cout << cntr + 1 << endl;

Using a standard Euler style GCD algorithm you can find easily off the web, this would be drastically better than what you are doing.

Try the iterative GCD funciton from here:GCD function in c++ sans cmath library

If this isnt good enough for your purposes (which it may not be) then I encourage you to search the web for one of several faster approaches. but, it may help in that searching to know that you are looking for the Euler Totient function: http://en.wikipedia.org/wiki/Euler%27s_totient_function

Answer 3

Well to make it work for larger n values replace all int's with long int's and if you are using c++11 you could use long long int's if that still is not enough. To make it run faster you could just before the outer for loop add

/*reserve Some value that is close to the outcome*/
num.reserve(n/2);

this will help but not alot.