A number can have a prime factor greater than its sqrt.

That's ok. You only need to generate primes up to sqrt(1 billion)
to test primality efficiently. For primes bigger than the sqrt, just
loop through the primes less than the sqrt and see if any of them
divide it. If not, it must be prime. I used this method for AC in 0.154.

I had the same problem in 10179. Fixing the special case for the input "1" gave me AC

But I don't really understand why the output in that case should be 1, since in the example given in the problem text, they don't count 0/12 as a irreducible basic fraction... Isn't this inconsistent?

[..in the example given in the problem text, they don't count 0/12 as a irreducible basic fraction..]

That is correct 0/12 can be reduced to any fraction with a non-zero denominator (e.g.0/1 etc.)

Problem 10179 differs from 10299 in that when n=1 there is an allowable irreducible fraction of 1/1 giving a count of 1.

In 10299 the problem description asks for the number of positive integers less than n which are relatively prime to n. For n=1 this is 0. Interestingly the EulerPhi function in Mathematica returns 1 for n=1!

int main()
{
unsigned long int m,n,x,vet[MAX]={0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
long int j=0,i=0;
float result1=0,fator=0;
long int r;
while(scanf("%ld",&m)==1)
{
if ((m>1000000000)||(m==0)) return 0;
x=2;n=m;i=0;
while (n>1)
{
r=n%x;
if (r==0)
{
if (x != vet)
{
i++;
vet=x;
}
n=n/x;
}
else if (n==x)
break;
else
x++;
}
result1 = m;
for (j=1;j<=i;j++)
{
fator=1;
fator/=vet[j];
result1 *= (1-fator);
}
printf("%ld\n",( unsigned long int)result1);
}
return 1;
}

Well, I think output for 1 is 1.
because, my compiler shows gcd(0,1) = 1 and the problem statement states,

A fraction m / n is basic if 0 <= m < n and it is irreducible if gcd(m, n) = 1.

I am to mention that I use Euclid's algorithm like others to find gcd(m,n).

So, i think (0,1) is considered to be an irreducible fraction in this sense and this helped me to get acc quite on the first submission. . . .looking for your further correction .

When i run the loop upto sqrt(n) i get WA because not all the prime factors are below sqrt(n) for example 123456.
But when i do it upto n/2, i get TLE. Please help. Thanks

Taman wrote:Well, I think output for 1 is 1.
because, my compiler shows gcd(0,1) = 1 and the problem statement states,

A fraction m / n is basic if 0 <= m < n and it is irreducible if gcd(m, n) = 1.

I am to mention that I use Euclid's algorithm like others to find gcd(m,n).

So, i think (0,1) is considered to be an irreducible fraction in this sense and this helped me to get acc quite on the first submission. . . .looking for your further correction .

Thanks for this suggestion, I got several W.As due to this case

Have you ever...

Wanted to work at best companies?

Struggled with interview problems that could be solved in 15 minutes?