Page **2** of **2**

Posted: **Sun Aug 08, 2004 5:24 am**

by **Minilek**

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.

Posted: **Tue Oct 05, 2004 9:59 pm**

by **rbarreira**

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?

Posted: **Thu Oct 14, 2004 6:52 pm**

by **Piers Kennedy**

[..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!

[/quote]

### 10179 Time Limit Exceeded

Posted: **Wed Feb 01, 2006 4:01 pm**

by **athlon19831**

#include "iostream.h"

#include "stdio.h"

#include "string.h"

#include "math.h"

bool Gcd(long M,long N)

{

long Rem;

while(N>0)

{

Rem=M%N;

M=N;

N=Rem;

}

if(M==1)

return true;

else

return false;

}

int main(int argc, char* argv[])

{

long n;

long i,j;

long num;

while(cin>>n)

{

if(n==0)

break;

else

{

num=0;

for(i=0;i<n;i++)

{

if(Gcd(n,i))

{

num++;

}

}

cout<<num<<endl;

}

}

return 0;

}

Posted: **Wed Feb 01, 2006 5:24 pm**

by **mamun**

Test your program with the maximum input, 999999999. You'll feel the speed of your program.

Find Euler's Phi function.

### 10179 Time Limit Exceeded

Posted: **Wed Apr 05, 2006 9:57 pm**

by **szwesley001**

Why?

/* @BEGIN_OF_SOURCE_CODE */

#include <stdio.h>

#define MAX 1000

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;

}

/* @END_OF_SOURCE_CODE */

Posted: **Wed Apr 05, 2006 11:40 pm**

by **Moha**

You post in the wrong Volume. see

http://online-judge.uva.es/board/viewto ... ght=10179
and before making a new subject, search in froum.

### 10179!!!! WA!!!Plz Help

Posted: **Mon May 22, 2006 4:26 pm**

by **sohel_acm**

Hi Solvers,

I am getting wa in 10179.But I can't find the bug in my code.Plz someone help me.Here is my code

Thanx in advance.

Posted: **Tue May 23, 2006 11:16 am**

by **sohel_acm**

I have found my error.At last I got ACC.

### Re: 10179 - Irreducible Basic Fractions

Posted: **Wed Aug 20, 2008 10:20 pm**

by **rhsumon**

WA plz help

first time TLE then WA where is the wrong

Code: Select all

```
#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#define P 100000
long prime[P];
long p[50000];
int phi[P+100];
void gen_prime(){
int i,j;
prime[0] = prime[1] = 1;
for(i=2; i<=(long)sqrt(P); i++){
if(prime[i]==0){
for(j=i*i; j<=P-1; j=j+i){
prime[j]=1;
}
}
}
j=0;
for(i=0; i<=P-1; i++){
if(prime[i] == 0){
p[j++] = i;
}
}
}
void phgen(){
int i,j;
for(i=2;i<=P;i++)
phi[i]=i;
for(i=2;i<=P;i++){
if(!prime[i]){
for(j=i;j<=P;j+=i)
phi[j]-=phi[j]/i;
}
}
}
int is_prime(int a){
int i;
for(i=0; p[i]*p[i]<=a; i++){
if(a%p[i]==0) return 0;
}
return 1;
}
int main()
{
gen_prime();
phgen();
int n,pi,i,flag;
while(scanf("%d",&n)==1 && n){
if(n==1) printf("1\n");
else if(n <= P) printf("%d\n",phi[n]);
else{
if(is_prime(n)) printf("%d\n",n-1);
else{
pi=1;
for(i=0; n!=1&&p[i]*p[i]<=n; i++){
flag=0;
while(n%p[i]==0){
pi*=p[i];
n/=p[i];
flag=1;
}
if(flag==1) pi-=pi/p[i];
if(is_prime(n)&&n>1){
pi*=(n-1);
break;
}
}
}
printf("%d\n",pi);
}
}
return 0;
}
```

### Re: 10179 - Irreducible Basic Fractions

Posted: **Mon Oct 06, 2008 8:16 am**

by **stcheung**

Your program outputs an extra line for primes larger than 100000. Try it with 100003.

### Re: 10179 - Irreducible Basic Fractions

Posted: **Fri Jan 01, 2010 2:20 pm**

by **Taman**

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

.

### Re: 10179 - Irreducible Basic Fractions

Posted: **Thu Mar 31, 2011 1:43 pm**

by **Pro.metal**

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

Code: Select all

```
#include <stdio.h>
#include <math.h>
char prime[1000000000];
int main()
{
long long n,prod,i,j,k;
long long d;
for(i=2; i<10000; i+=2)
{
if(prime[i]==0)
{
for(j=i*i; j<10000000; j+=i) prime[j] = 1;
}
if(i==2) i = i - 1;
}
while(scanf("%lld",&n)!=EOF)
{
if(!n) break;
prod = n;
for(k=2; k<n/2; k++)
{
if(n%k==0 && !prime[k])
{
prod = prod *(k-1) / k;
}
}
printf("%lld\n",prod);
}
return 0;
}
```

### Re: 10179 - Irreducible Basic Fractions

Posted: **Fri Apr 01, 2011 10:39 pm**

by **DD**

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