-3

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;
}
DanielV
  • 209
  • 1
  • 3
  • 13
  • 2
    What do you think is slowing your program down? Have you done any benchmarking? "Fix my program for me" is not a good type of question on this site. – Floris Jan 12 '14 at 23:18
  • 1
    I think [CodeReview](http://codereview.stackexchange.com/) is better place for this question – Bryan Chen Jan 12 '14 at 23:20
  • I said that sometimes n is to big for example n=1000000000 my program doesn't work because this number is too big!!!!!So I want to fix this!! – DanielV Jan 12 '14 at 23:21
  • thi is an algorithm tag question as much as C++ – RichardPlunkett Jan 12 '14 at 23:21
  • Are you saying it takes too long, or that it actually fails? You are using `int` for the data type. That might have a range of -32k to +32k - much too small to hold 1E9. You would need at least a `long int` which is 4 bytes. – Floris Jan 12 '14 at 23:22
  • @Floris I think because off to for is slow I should try to make it one but I don't know how could reduce two for in one and get answer!!!! – DanielV Jan 12 '14 at 23:24
  • 2
    Well, this is an O(N^2) algorithm, thats pretty poor for this task. So, I suspect he issue is just speed, rather than say a sub-32 int architecture. – RichardPlunkett Jan 12 '14 at 23:25
  • @Floris I change my code int into long but still It's slow!!!! – DanielV Jan 12 '14 at 23:27
  • @Danial, I think Floris meant you to use `long`, not `long long` – RichardPlunkett Jan 12 '14 at 23:30
  • @BryanChen codereview isn't really good for fixing a bad algorithm. – Wooble Jan 12 '14 at 23:30
  • 1
    Don't you just need to verify that the GCD(x, y) == 1 for them to be relatively prime. For example, the GCD(15, 95) == 5 so they are not relatively prime, but GCD(15, 94) == 1 so they are relatively prime. This is a heap faster than any O(N*N) algorithm such as the one you show. – Jonathan Leffler Jan 12 '14 at 23:31
  • that would be a fine comment if you had made it before my answer, rather than after ... – RichardPlunkett Jan 12 '14 at 23:46
  • There is a much faster way to do this - it is given as an answer to an earlier question about the same topic. See http://stackoverflow.com/a/1019389/1967396 . Google is your friend. – Floris Jan 12 '14 at 23:52
  • possible duplicate of [How many numbers below N are coprimes to N?](http://stackoverflow.com/questions/1019040/how-many-numbers-below-n-are-coprimes-to-n) – Floris Jan 12 '14 at 23:54
  • @Floris it would certainly be a duplicate if similar languages were in play. – RichardPlunkett Jan 13 '14 at 00:29
  • @RichardPlunkett I think we established fairly quickly that this is really an algorithm question, not a C++ question (except possibly for the size of the container). Since the question I linked has no language tag, asks for exactly this algorithm, and includes a very useful answer with a very efficient algorithm for solving exactly this problem , I consider it a fair "possible duplicate". – Floris Jan 13 '14 at 01:10
  • @Floris. Yep, all fair points. – RichardPlunkett Jan 13 '14 at 02:06

3 Answers3

3

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

Community
  • 1
  • 1
RichardPlunkett
  • 2,988
  • 13
  • 14
  • Unfortunately your code does't work either. I want to work for n=1000000000 it's too slow!!! – DanielV Jan 12 '14 at 23:37
  • GCD is O(logN), so this alg is O(NlogN) running it for 1 billion cycles on a modern machine will be sluggish. Still, I think you will find that it a) does terminate eventually, unlike yours, and b) terminates in a reasonable time for much higher values than yours. – RichardPlunkett Jan 12 '14 at 23:41
  • I know your program is good and faster than mine.but there isn't any other algorithm for this question that work for that value????? – DanielV Jan 12 '14 at 23:46
  • 2
    well I expect you can factorize N in O(sqrt(N)) time, and calculate the totient from that (its very very tricky code tho). – RichardPlunkett Jan 12 '14 at 23:48
  • @RichardPlunkett maybe not so tricky? – Will Ness Jan 13 '14 at 09:29
  • ok, the thing I was thinking of at the time would have been tricky, but yes, it seems there are simple ways to use the factorisation to get the answer. – RichardPlunkett Jan 15 '14 at 01:03
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.

Floris
  • 45,045
  • 6
  • 64
  • 115
-1

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.

user2445735
  • 156
  • 1
  • 5