| Author |
program optimization... |
shivmitra
Member
Posts: 2
Location:
Joined: 29.03.09
Rank: Hacker Level 1 |
|
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 ≤ N ≤ 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: 2009-05-05
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... |
M4RCUSZ
Member
Posts: 14
Location:
Joined: 24.05.09
Rank: Newbie |
|
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... |
Pwnzall
Member
Posts: 234
Location:
Joined: 10.04.08
Rank: Hacker Level 3 |
|
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.
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++)
#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
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: 4190
Location: The Netherlands
Joined: 14.04.07
Rank: God
Warn Level: 90
|
|
Homework thread.
Wheeeeeeee.
"The chowner of property." - Zeph 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 |
|
| Author |
RE: program optimization... |
c4p_sl0ck
Member
Posts: 380
Location: Sweden
Joined: 17.09.06
Rank: God |
|
|
spyware wrote:
Homework thread.
Wheeeeeeee.
Indeed, that was my first thought as well.
 |
|
| Author |
RE: program optimization... |
styloverte116
Member
Posts: 73
Location:
Joined: 11.03.08
Rank: Hacker Level 3 |
|
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... |
1337h4cker
Member
Posts: 6
Location:
Joined: 04.06.09
Rank: Apprentice |
|
|
go to your teacher if you cant solve it |
|
|
| Author |
RE: program optimization... |
styloverte116
Member
Posts: 73
Location:
Joined: 11.03.08
Rank: Hacker Level 3 |
|
|
1337h4cker wrote:
go to your teacher if you cant solve it
depends on the teacher... sometimes they're ass holes. |
|
|
| Author |
RE: program optimization... |
Pwnzall
Member
Posts: 234
Location:
Joined: 10.04.08
Rank: Hacker Level 3 |
|
|
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.
Pure madness! There must be a method! There is a method! |
|
|
| Author |
RE: program optimization... |
fashizzlepop
Member
Posts: 482
Location: Old folks home.
Joined: 08.04.08
Rank: Uber Elite |
|
|
shivmitra wrote:
given a number N, compute the product of its positive divisors.
You might want to re-read 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~
 |
|
|
Main:
