C++

Forum

 
GCD

samarth123 (53)
i wanted to find the summation of gcd(i,n) from i=1 to i=n.
I have to input the value of 'n'.
The time limit for the code to run is 1.5 sec.
and 1<=n<=10^7.
What is the best way to optimise the code to run.
Last edited on
closed account (E3h7X9L8)
what is gcd and can you provide what you've coded
JayhawkZombie (738)
We can't just give you the answers.

What code have you written so far?

Have you tried using the Euclidean Algorithm?
samarth123 (53)
gcd stands for "greatest common divisor".
This is my code.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
 
#include<iostream>
#include<stdio.h>
#include <math.h>
using namespace std;

int readint()
{
   int cc = getc(stdin);
   for (;cc < '0' || cc > '9';)  cc = getc(stdin); //ignores char stream other than 0-9.
   int ret = 0;
   for (;cc >= '0' && cc <= '9';) // if stream of numbers comes, start taking input
   {
      ret = ret * 10 + cc - '0'; // convert each char to integral digit and extend the final number 
      cc = getc(stdin);          // input continues
   }
  return ret;                   // return final extended number.
}


// A function to print all prime factors of a given number n
int phi(int n)
{    
    int result = n;   // Initialize result as n
    //int a[n];
    //for(int i=0;i<n-1;i++)
    //{
    //	a[i]=0;
//    }
	//a[n-1]=1;
 
    // Consider all prime factors of n and subtract their
    // multiples from result
    for (int p=2; p*p<=n; ++p)
    {
        // Check if i is a prime factor.
        if (n % p == 0)
        {
            // If yes, then update n and result 
            while (n % p == 0)
				 {
				  n /= p;
				  //a[n-1]=1;
			     }
            result -= result / p;
        }
    }
 
    // If n has a prime factor greater than sqrt(n)
    // (There can be at-most one such prime factor)
    if (n > 1)
        result -= result / n;
  return result ;

}
int main()
{
	int t,n;
	t=readint();
	while(t--)
	{
    n=readint();
    unsigned long long a[n+1];
	unsigned long long b[n+1];
    for(int i=0;i<=n;i++)
    {
    	a[i]=0;
	}
	for(int i=0;i<=n;i++)
    {
    	b[i]=0;
	}
	
    for(int i=1;i<=sqrt(n);i++)
    {
        if(n%i==0)
        {
       // cout<<i<<" " <<n/i<<" ";
           a[i]=i;
		   a[n/i]=n/i;  
        }
    }
      int sum=0;
      for(int i=0;i<=n;i++)
      {
      	if(a[i]!=0)
      	{
      	  	b[i]=i*phi(i);
      	     //b[i]=n/b[i];
      	     sum=sum+b[i];
		}
	  }
	  printf("%d\n",sum);
/*	  int sum=0;
	  for(int i=0;i<=n;i++)
	  {
	  	if(b[i]!=0)
	  	{
	  		sum=sum+b[i];
		}
	  }
	  cout<<sum<<"\n";
	  */
    }
}


some of the test cases are showing run time error while some are showing time limit exceeded..please help me out.
Please help me out
Last edited on
samarth123 (53)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
 
#include<iostream>
#include<stdio.h>
#include <math.h>
using namespace std;

int readint()
{
   int cc = getc(stdin);
   for (;cc < '0' || cc > '9';)  cc = getc(stdin); //ignores char stream other than 0-9.
   int ret = 0;
   for (;cc >= '0' && cc <= '9';) // if stream of numbers comes, start taking input
   {
      ret = ret * 10 + cc - '0'; // convert each char to integral digit and extend the final number 
      cc = getc(stdin);          // input continues
   }
  return ret;                   // return final extended number.
}


// A function to print all prime factors of a given number n
int phi(int n)
{    

    int result = n;   // Initialize result as n
    //int a[n];
    //for(int i=0;i<n-1;i++)
    //{
    //	a[i]=0;
//    }
	//a[n-1]=1;
 
    // Consider all prime factors of n and subtract their
    // multiples from result
    for (int p=2; p*p<=n; ++p)
    {
        // Check if i is a prime factor.
        if (n % p == 0)
        {
            // If yes, then update n and result 
            while (n % p == 0)
				 {
				  n /= p;
				  //a[n-1]=1;
			     }
            result -= result / p;
        }
    }
 
    // If n has a prime factor greater than sqrt(n)
    // (There can be at-most one such prime factor)
    if (n > 1)
        result -= result / n;
  return result ;

}
int main()
{
	int t,n;
	t=readint();
	while(t--)
	{
    n=readint();
    //unsigned long long a[n+1];
	//unsigned long long b[n+1];
    /*for(int i=0;i<=n;i++)
    { 
    	a[i]=0;
	}*/
	/*for(int i=0;i<=n;i++)
    {
    	b[i]=0;
	}*/
	    unsigned long long c,d;
	   unsigned long long sum=0;
    for(int i=1;i<=sqrt(n);i++)
    {
        if(n%i==0)
        {
       // cout<<i<<" " <<n/i<<" ";
           //a[i]=i;
		   //a[n/i]=n/i;
		   c=i*phi(i);
		   d=(n/i)*phi(n/i);
		   if(c!=d)
		   {
			sum=sum+c+d;
		   }
		   if(c==d)
		   {
			sum=sum+c;
		   }
		   
        }
    }
     /*  unsigned long long sum=0;
      for(int i=0;i<=n;i++)
      {
      	if(a[i]!=0)
      	{
      	  	b[i]=i*phi(i);
      	     //b[i]=n/b[i];
      	     sum=sum+b[i];
		}
	  }*/
	  printf("%d\n",sum);
    /*	  int sum=0;
	  for(int i=0;i<=n;i++)
	  {
	  	if(b[i]!=0)
	  	{
	  		sum=sum+b[i];
		}
	  }
	  cout<<sum<<"\n";
	  */
    }
}

This is a bit more opitmised code .But it is still showing time limit exceeded.
Last edited on
Topic archived. No new replies allowed.