Unfortunantly It Runs too slow :(

[khengol khan]

I Want to solve problem 69 of project euler, It is correct But It Runs too slow!! Damn it!! :(
How Can I Speed Up this?!? Any Ideas??!?

#include <iostream>
#include <cmath>
using namespace std;
float totient( int n){
	long int primeto=0,i,j;
	float totient;
	for (i=1;i<=n;i++){
	int count=0;
	for (j=1;j<=i;j++){
		if (n%j==0 && i%j==0) count++;
	}
	if(count==1) primeto++;
}
totient=(float) n/primeto;
return totient;
}
int main(){
	long int n,max_n;
	float max_t=0; 
	for (n=1;n<=1000000;n++) {
		if (totient(n)>max_t){
			max_t=totient(n);
			max_n=n;
		}
}
cout << max_n<< "  " << max_t<<endl;
}

[MikeyBoy]

Do you mean it runs too slow?

[khengol khan]

Do you mean it runs too slow?

Yeah :D :D Sry , I was Confused for fighting with this problem!

[Computergeek01]

Take a look here: http://en.wikipedia.org/wiki/Prime_number#Testing_primality_and_integer_factorization

I'm not going to give away anymore because that's sort of the point of these activities.

[khengol khan]

Take a look here: http://en.wikipedia.org/wiki/Prime_number#Testing_primality_and_integer_factorization

I'm not going to give away anymore because that's sort of the point of these activities.

I dont want to check if the number is prime or not!! :S

I want to determine the number of numbers less than n which are relatively prime to n!

Check this : http://projecteuler.net/problem=69

[TheIdeasMan]

The project Euler problems are not as straight forward as you might think - you have to come up with a cunning plan (is that what Computergeek01 is hinting at ?)

Often the problem with the most obvious solution is that it loops 1 trillion much more than 1,000 quadrillion times and is hence too slow. This is where Project Euler is awesome - it requires some special techniques to solve them, so there is lots of learning to be had.

Hope all goes well :+)

Edit : 1 Quadrillion = 1,000 trillion

Edit 2: thought about it more. 1,000,000 * 1,000,000 * sum(1 to 1 million)

[Chervil]

A minor suggestion, though I think it will require more thought than this:

    if (totient(n)>max_t){
        max_t=totient(n);
        max_n=n;
    }

Here the function totient() is called twice, at both lines 21 and 22. It would be better to store the result of the first call in a temporary variable to avoid the need to call the function again.

[ne555]

> I want to determine the number of numbers less than n which are relatively prime to n
No, you don't.
You want to determine the number n for which n/\phi(n) is maximum

Think what interesting property such a number would have. Test your conjecture with smaller limits (you've already got lim<10, try lim<100 and lim<1000)
then prove it, or just give it a shot.


To know if two numbers are relative prime, you could test gcd(a,b) = 1

[khengol khan]

> I want to determine the number of numbers less than n which are relatively prime to n
No, you don't.
You want to determine the number n for which n/\phi(n) is maximum

I mean i want to store " the number of numbers less than n which are relatively prime to n " in primeto !

[ne555]

and I mean that you don't need to.

(to abbreviate, lets call f(n) = n/\phi(n) )
From the table you can see that
f(2) = f(4) = f(8)
f(3) = f(9)
f(2) > f(3) > f(5) > f(7)
f(6) > f(10)

try to understand why this is happening, then you could relate
f(16) to f(8)
f(11) to f(7)
f(15) to f(10) and f(6)
f(18) to f(9)
without actually computing `f'

and later use that knowledge to find `n' for which `f(n)' is maximum

[khengol khan]

and I mean that you don't need to.

(to abbreviate, lets call f(n) = n/\phi(n) )
From the table you can see that
f(2) = f(4) = f(8)
f(3) = f(9)
f(2) > f(3) > f(5) > f(7)
f(6) > f(10)

try to understand why this is happening, then you could relate
f(16) to f(8)
f(11) to f(7)
f(15) to f(10) and f(6)
f(18) to f(9)
without actually computing `f'

and later use that knowledge to find `n' for which `f(n)' is maximum

I didnt notice this!!

It seems to be helpful!! not solved yet, but just working on it!! ;)

By The way tnx