Author  program optimization... 
Member
Posts: Location:
Joined: 01.01.70 Rank: Guest  
Being in love with number theory, Johnny decided to take a number theory course. On the first day, he was challenged by his teacher with the following problem: given a number N, compute the product of its positive divisors. Johnny is desperate to impress his new teacher so he asks you for help.
In this problem, the divisors of N do not include the number N itself. For example, if N=12, the divisors of N (excluding N) are 1, 2, 3, 4, and 6. Thus, the product of divisors is 1x2x3x4x6=144. Since the result may be very large, if the result has more than 4 decimal digits, Johnny only needs to compute the last 4 digits of it.
Input
The first line contains t, the number of test cases (about 300,000). Then t test cases follow.
Each test case contains a single integer N (2 x04; N x04; 500,000) whose product of divisors needs to be computed.
Output
For each test case, print a single line containing the corresponding result of that test case.
Example
Input
6
3
4
12
25
957
10000
Output
1
2
144
5
7493
0000
Date: 20090505
Time limit: 2s
Source limit: 50000B
Languages: All
i hav written code using brute forcing approach.but time limit of 2s exceeds.hw can i reduce time limit.Tell me if my approach is wrong...
my code is below
#include<stdio.h>
//#include<conio.h>
int main()
{
register long int t;
scanf("%d",&t);
for(register long int y=0;y<t;y++)
{
long int mul=1;
long int n;
int x=0;
scanf("%ld",&n);
for(register long int i=2;i<=n/2;i++)
{
if(n%i==0)
{
mul=mul*i;
if((mul/10000)!=0)
{
mul=mul%10000;
x=1;
}
}
}
if(x==1 && mul==0)
printf("0000\n";
else
printf("%ld\n",mul);
}
//getch();
}
thanx for reading.... 

Author  RE: program optimization... 
Member
Posts: Location:
Joined: 01.01.70 Rank: Guest  
This is the wrong site to ask, most people will just say piss of and learn yourself.
Try to use google it will probably give you a better answers or ask on a site dedicated to help people with programming.


Author  RE: program optimization... 
Member
Posts: Location:
Joined: 01.01.70 Rank: Guest  
Well for one, you dont have to iterate the loop all the way until you reach N. You can safely stop at N/2 because usually the last or largest factor (excluding N) comes before or right at N/2. And if you have to get N included as a factor, you can just multiply the product of your divisors by N as a separate step.
You could make a chart to prove it.
Code
N..........N/2..........Largest factor (excluding N)
6...........3............3
8...........4............4
9.........4.5...........3
10.........5............5
12.........6............6
14.........7............7
...etc
I whipped up a little bit of code and noticed at 25, you got 5. Are you not supposed to list factors that occur more than once? I'm rusty and haven't coded in a while, but here's what I have (in C++)
Code
#include <iostream>
#include <conio.h>
using namespace std;
int main(){
//get number
int number;
unsigned long int productofdivisors=1;
cin>>number;
for(int i=1;i<=(number/2);i++){
/*I did number/2 because i noticed usually after half the number i reached, there are no more factors except for whatever the number is itself.*/
if(number%i==0){
productofdivisors*=i;
}
}
cout<<productofdivisors;
getch();
return 0;
}
Replacing the contents of the for loop with
Code
if(sqrt(number)==i){
productofdivisors*=(i*i);
}
else{
productofdivisors*=i;
}
catches cases where a factor occurs more than once in a number like 25 (where 5 occurs twice). 

Author  RE: program optimization... 
spyware Member
Posts: 4192 Location: The Netherlands
Joined: 14.04.07 Rank: God Warn Level: 90
 
Homework thread.
Wheeeeeeee.
"The chowner of property."  Zeph [small]“Widespread intellectual and moral docility may be convenient for leaders in the short term,
but it is suicidal for nations in the long term.”  Carl Sagan “Since the grid is inescapable, what were the earlier lasers about? Does the corridor have a sense of humor?”  Ebert [/s 

Author  RE: program optimization... 
Member
Posts: Location:
Joined: 01.01.70 Rank: Guest  
spyware wrote:
Homework thread.
Wheeeeeeee.
Indeed, that was my first thought as well.


Author  RE: program optimization... 
Member
Posts: Location:
Joined: 01.01.70 Rank: Guest  
you don't have to go to N/2. only the square root of N, cause youll already have figured out the higher divisors by doing N/lowerDivisor.
spy and caps... hes learning... hw isnt always best done by yourself. he provided code.. of which i didnt look at but im sure he put some effort in. 

Author  RE: program optimization... 
Member
Posts: Location:
Joined: 01.01.70 Rank: Guest  
go to your teacher if you cant solve it 

Author  RE: program optimization... 
Member
Posts: Location:
Joined: 01.01.70 Rank: Guest  
1337h4cker wrote:
go to your teacher if you cant solve it
depends on the teacher... sometimes they're ass holes. 

Author  RE: program optimization... 
Member
Posts: Location:
Joined: 01.01.70 Rank: Guest  
styloverte116 wrote:
you don't have to go to N/2. only the square root of N, cause youll already have figured out the higher divisors by doing N/lowerDivisor.
spy and caps... hes learning... hw isnt always best done by yourself. he provided code.. of which i didnt look at but im sure he put some effort in.
All too true, I'm embarassed that I knew that but didn't think of it.


Author  RE: program optimization... 
fashizzlepop Member
Posts: 482 Location: Old folks home.
Joined: 08.04.08 Rank: Moderate  
shivmitra wrote:
given a number N, compute the product of its positive divisors.
You might want to reread your problem first. Saved your grade.
"The definition of insanity is doing the same thing over and over again and expecting different results.”
~Albert Einstein~

